Покраска прямоугольников в матрице — разбор

1. Идея

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

Если обновлять все клетки каждого прямоугольника напрямую, то одна операция может затронуть до n * m элементов. При k до 2 * 10^5 это слишком медленно.

Главная идея — использовать двумерный разностный массив.
Он позволяет делать прибавление на прямоугольнике за O(1), а потом один раз восстановить итоговую матрицу с помощью двумерных префиксных сумм.

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

Наблюдение 1. Как работает одномерный разностный массив

В одномерном массиве, чтобы прибавить v на отрезке [l..r], можно сделать:

• diff[l] += v
• diff[r + 1] -= v

После этого обычная префиксная сумма по diff восстановит итоговый массив.

Наблюдение 2. То же самое можно сделать в двумерном случае

Для прямоугольника с углами (r1, c1) и (r2, c2) нужно:

• diff[r1][c1] += v
• diff[r1][c2 + 1] -= v
• diff[r2 + 1][c1] -= v
• diff[r2 + 1][c2 + 1] += v

После всех таких операций итоговое значение клетки получается двумерной префиксной суммой.

Наблюдение 3. Почему это удобно здесь

• прямоугольных обновлений много;
• запросы точечные;
• размеры матрицы n, m <= 1000, значит полную матрицу n * m можно восстановить целиком.

Матрица максимум 1000 * 1000 = 10^6 клеток — это нормально и по времени, и по памяти.

3. Алгоритм

1. Считываем n, m, k, q.
2. Создаём двумерный массив diff размера (n + 2) x (m + 2), заполненный нулями. Дополнительные границы нужны, чтобы безопасно обращаться к r2 + 1 и c2 + 1.
3. Для каждого прямоугольника (r1, c1, r2, c2, v) делаем:
   • diff[r1][c1] += v
   • diff[r1][c2 + 1] -= v
   • diff[r2 + 1][c1] -= v
   • diff[r2 + 1][c2 + 1] += v
4. Создаём массив a размера (n + 1) x (m + 1), где будем хранить итоговые значения.
5. Восстанавливаем итоговую матрицу по формуле двумерной префиксной суммы:
   • a[i][j] = diff[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]
6. Для каждого запроса (r, c) выводим a[r][c].

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

Покажем, почему четыре изменения в diff действительно прибавляют v ко всем клеткам прямоугольника и только им.

Рассмотрим одну операцию с прямоугольником (r1, c1, r2, c2) и значением v.

Мы записываем:

• в левом верхнем углу +v,
• справа от прямоугольника -v,
• снизу от прямоугольника -v,
• в клетке по диагонали снизу-справа +v.

Когда потом строится двумерная префиксная сумма, каждая клетка (i, j) получает сумму всех diff[x][y], где x <= i и y <= j.

Что произойдёт:

• если клетка находится внутри прямоугольника, то в её префиксную сумму попадёт только +v из (r1, c1), а компенсирующие вычитания ещё не попадут;
• если клетка находится правее прямоугольника, то в сумму попадут и +v, и -v справа, они сократятся;
• если клетка находится ниже прямоугольника, то аналогично сократятся +v и -v снизу;
• если клетка находится ниже и правее, то попадут все четыре изменения, и итог снова станет 0.

Значит, вклад этой операции равен:

• v для клеток внутри прямоугольника,
• 0 для всех остальных.

Так как операции независимы, их вклады просто складываются. Следовательно, после обработки всех прямоугольников и восстановления префиксами значение a[i][j] равно сумме всех добавлений в клетку (i, j).

5. Сложность

Пусть матрица имеет размер n x m.

• Обработка всех k прямоугольников: O(k)
• Восстановление всей матрицы: O(n * m)
• Ответы на q запросов: O(q)

Итоговая сложность:

• O(k + n * m + q)

Память:

• O(n * m)

При n, m <= 1000 это подходит.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

    vector<vector<long long>> diff(n + 2, vector<long long>(m + 2, 0));

    for (int i = 0; i < k; i++) {
        int r1, c1, r2, c2;
        long long v;
        cin >> r1 >> c1 >> r2 >> c2 >> v;

        diff[r1][c1] += v;
        if (c2 + 1 <= m + 1) diff[r1][c2 + 1] -= v;
        if (r2 + 1 <= n + 1) diff[r2 + 1][c1] -= v;
        if (r2 + 1 <= n + 1 && c2 + 1 <= m + 1) diff[r2 + 1][c2 + 1] += v;
    }

    vector<vector<long long>> a(n + 1, vector<long long>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = diff[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }

    for (int i = 0; i < q; i++) {
        int r, c;
        cin >> r >> c;
        cout << a[r][c] << '\n';
    }

    return 0;
}

7. Код на Python 3

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

diff = [[0] * (m + 2) for _ in range(n + 2)]

for _ in range(k):
    r1, c1, r2, c2, v = map(int, input().split())
    diff[r1][c1] += v
    diff[r1][c2 + 1] -= v
    diff[r2 + 1][c1] -= v
    diff[r2 + 1][c2 + 1] += v

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

for i in range(1, n + 1):
    for j in range(1, m + 1):
        a[i][j] = diff[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]

for _ in range(q):
    r, c = map(int, input().split())
    print(a[r][c])