Подсчёт особых клеток в прямоугольнике — разбор

1. Идея

Нужно много раз отвечать на вопрос: сколько единиц находится внутри прямоугольника бинарной матрицы.

Если для каждого запроса просто перебирать все клетки внутри прямоугольника, то это будет слишком долго: прямоугольник может быть большим, а запросов до 2 * 10^5.

Значит, нужно один раз сделать предварительную обработку матрицы, чтобы потом каждый запрос обрабатывать очень быстро.

Для этого используется двумерная префиксная сумма.

2. Наблюдения

Пусть p[i][j] — количество единиц в прямоугольнике от (1, 1) до (i, j) включительно.

Тогда p[i][j] можно посчитать по формуле:

p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j]

Почему так:

• p[i - 1][j] — всё сверху,
• p[i][j - 1] — всё слева,
• общая часть p[i - 1][j - 1] посчиталась дважды, поэтому её надо вычесть,
• потом добавляем значение текущей клетки.

Теперь рассмотрим запрос: дан прямоугольник с углами (r1, c1) и (r2, c2).

Количество единиц в нём можно получить из префиксных сумм так:

answer = p[r2][c2] - p[r1 - 1][c2] - p[r2][c1 - 1] + p[r1 - 1][c1 - 1]

Это обычное включение-исключение для прямоугольников.

Чтобы не думать о выходе за границы, удобно хранить массив p размера (n + 1) x (m + 1) и считать, что строка 0 и столбец 0 заполнены нулями.

3. Алгоритм

1. Считываем n, m, q.
2. Создаём таблицу p размера (n + 1) x (m + 1), заполненную нулями.
3. Для каждой клетки матрицы:
   • читаем символ '0' или '1',
   • переводим его в число 0 или 1,
   • считаем p[i][j] по формуле двумерной префиксной суммы.
4. Для каждого запроса:
   • считываем r1, c1, r2, c2,
   • вычисляем ответ по формуле через p,
   • выводим его.

4. Почему это работает

Докажем корректность.

Почему правильно считается p[i][j]

По определению, p[i][j] — это число единиц в прямоугольнике с углами (1, 1) и (i, j).

Возьмём:

• прямоугольник (1, 1) ... (i - 1, j),
• прямоугольник (1, 1) ... (i, j - 1).

Вместе они покрывают весь нужный прямоугольник, кроме того что общая часть (1, 1) ... (i - 1, j - 1) учитывается два раза. Поэтому её нужно один раз вычесть. После этого остаётся добавить значение клетки (i, j).

Именно это делает формула:

p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j]

Значит, все значения p вычисляются верно.

Почему правильно считается ответ на запрос

Рассмотрим весь префиксный прямоугольник (1, 1) ... (r2, c2). В нём содержится нужный прямоугольник, но ещё есть лишние части:

• строки выше r1, то есть прямоугольник (1, 1) ... (r1 - 1, c2),
• столбцы левее c1, то есть прямоугольник (1, 1) ... (r2, c1 - 1).

Если их просто вычесть, то верхний левый угол (1, 1) ... (r1 - 1, c1 - 1) вычтется дважды, поэтому его нужно вернуть обратно.

Получаем формулу:

p[r2][c2] - p[r1 - 1][c2] - p[r2][c1 - 1] + p[r1 - 1][c1 - 1]

Значит, для каждого запроса мы действительно получаем количество единиц внутри заданного прямоугольника.

5. Сложность

Построение таблицы префиксных сумм:

• O(n * m)

Обработка одного запроса:

• O(1)

Общая сложность:

• O(n * m + q)

Память:

• O(n * m)

Это хорошо укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> p(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            int val = s[j - 1] - '0';
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + val;
        }
    }

    for (int k = 0; k < q; k++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        int ans = p[r2][c2] - p[r1 - 1][c2] - p[r2][c1 - 1] + p[r1 - 1][c1 - 1];
        cout << ans << '\n';
    }

    return 0;
}

7. Код на Python 3

n, m, q = map(int, input().split())

p = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    s = input().strip()
    for j in range(1, m + 1):
        val = ord(s[j - 1]) - ord('0')
        p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + val

for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    ans = p[r2][c2] - p[r1 - 1][c2] - p[r2][c1 - 1] + p[r1 - 1][c1 - 1]
    print(ans)