Editorial for City Lights Queries

Approach

Build a 2D prefix-sum table where $pref[r][c]$ is the number of lit windows in the rectangle from $(1, 1)$ to $(r, c)$.

Here, $r$ means row and $c$ means column, matching the query format $(r_1, c_1, r_2, c_2)$.

Let $arr[r][c]$ be $1$ if window $(r, c)$ is lit and $0$ otherwise. Then:

$pref[r][c] = arr[r][c] + pref[r][c - 1] + pref[r - 1][c] - pref[r - 1][c - 1]$

For a query rectangle $[r_1, r_2] \times [c_1, c_2]$, use inclusion-exclusion:

$pref[r_2][c_2] - pref[r_1 - 1][c_2] - pref[r_2][c_1 - 1] + pref[r_1 - 1][c_1 - 1]$

Building the table takes $O(n^2)$, and each query is answered in $O(1)$, so the total time complexity is $O(n^2 + q)$.

Solution (Python)

def main() -> None:
    n, q = map(int, input().split())
    prefix = [[0] * (n + 1) for _ in range(n + 1)]

    for r in range(1, n + 1):
        row = input().strip()
        for c, cell in enumerate(row, start=1):
            lit = 1 if cell == "*" else 0
            prefix[r][c] = lit + prefix[r][c - 1] + prefix[r - 1][c] - prefix[r - 1][c - 1]

    answers: list[str] = []
    for _ in range(q):
        r1, c1, r2, c2 = map(int, input().split())
        lit = prefix[r2][c2]
        lit -= prefix[r1 - 1][c2]
        lit -= prefix[r2][c1 - 1]
        lit += prefix[r1 - 1][c1 - 1]
        answers.append(str(lit))

    print("\n".join(answers))


if __name__ == "__main__":
    main()