Editorial for City Lights Queries

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

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

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

Let $arr[r][c]$ ~arr[r][c]~ be $1$ ~1~ if window $(r, c)$ ~(r, c)~ is lit and $0$ ~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]$ ~[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)$ ~O(n^2)~, and each query is answered in $O(1)$ ~O(1)~, so the total time complexity is $O(n^2 + q)$ ~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()

Comments

There are no comments at the moment.