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[y][x]$ ~pref[y][x]~ is the number of lit windows in the rectangle from $(1, 1)$ ~(1, 1)~ to $(y, x)$ ~(y, x)~.

While reading row $y$ ~y~, keep a running count $row_sum$ ~row_sum~ of lit windows seen so far in that row. Then:

$pref[y][x] = pref[y - 1][x] + row\_sum$

For a query rectangle $[y_1, y_2] \times [x_1, x_2]$ ~[y_1, y_2] \times [x_1, x_2]~, use inclusion-exclusion:

$pref[y_2][x_2] - pref[y_1 - 1][x_2] - pref[y_2][x_1 - 1] + pref[y_1 - 1][x_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)

import sys


def main() -> None:
    input = sys.stdin.buffer.readline

    n, q = map(int, input().split())
    prefix = [[0] * (n + 1) for _ in range(n + 1)]

    for y in range(1, n + 1):
        row = input().strip()
        running = 0
        current = prefix[y]
        previous = prefix[y - 1]
        for x, cell in enumerate(row, start=1):
            if cell == 42:
                running += 1
            current[x] = previous[x] + running

    answers: list[str] = []
    for _ in range(q):
        y1, x1, y2, x2 = map(int, input().split())
        lit = prefix[y2][x2]
        lit -= prefix[y1 - 1][x2]
        lit -= prefix[y2][x1 - 1]
        lit += prefix[y1 - 1][x1 - 1]
        answers.append(str(lit))

    sys.stdout.write("\n".join(answers) + "\n")


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.