Разбор задачи «Прибавления на подпрямоугольниках»

1. Идея

Наивно применять каждую операцию ко всем клеткам прямоугольника слишком дорого. Обобщим одномерный разностный массив на две координаты: одну операцию «прибавить v на прямоугольнике» можно записать четырьмя точечными изменениями, а итоговые значения восстановить двумерными префиксными суммами.

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

Заведём разностную таблицу d. Прибавление v на прямоугольнике (r1,c1)-(r2,c2) кодируется так:

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

После всех операций двумерная префиксная сумма d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1] превращает разностную таблицу в итоговые значения клеток.

3. Алгоритм

1. Обнулить разностную таблицу.
2. Для каждой операции применить четыре точечных изменения.
3. Пройти таблицу и накопить двумерные префиксные суммы, попутно обновляя максимум по всем клеткам.
4. Вывести максимум.

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

Каждая из четырёх меток задаёт, где вклад v «включается» и «выключается» по строкам и столбцам. Двумерное накопление префиксов суммирует все включённые вклады в каждой клетке, что в точности равно сумме значений v всех операций, покрывающих эту клетку.

5. Сложность

Операции обрабатываются за O(q), накопление префиксов — за O(r*c). Итого O(r*c + q) по времени и O(r*c) по памяти. Значения могут достигать порядка 10^9 умноженного на число операций, поэтому обязателен 64-битный тип. Максимум ищем среди фактических значений клеток (он может быть и отрицательным).

Код на C++17

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int main() {
    int r, c, q;
    cin >> r >> c >> q;

    vector<vector<long long>> d(r + 2, vector<long long>(c + 2, 0));

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

        d[r1][c1] += v;
        d[r1][c2 + 1] -= v;
        d[r2 + 1][c1] -= v;
        d[r2 + 1][c2 + 1] += v;
    }

    long long ans = numeric_limits<long long>::min();

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
            if (d[i][j] > ans) {
                ans = d[i][j];
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

Код на Python 3

import sys
data = sys.stdin.buffer.read().split()
idx = 0
R = int(data[idx]); C = int(data[idx+1]); q = int(data[idx+2]); idx += 3
diff = [[0] * (C + 2) for _ in range(R + 2)]
for _ in range(q):
    r1 = int(data[idx]); c1 = int(data[idx+1]); r2 = int(data[idx+2]); c2 = int(data[idx+3]); v = int(data[idx+4]); idx += 5
    diff[r1][c1] += v
    diff[r1][c2 + 1] -= v
    diff[r2 + 1][c1] -= v
    diff[r2 + 1][c2 + 1] += v

best = None
for i in range(1, R + 1):
    for j in range(1, C + 1):
        diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]
        best = diff[i][j] if best is None else max(best, diff[i][j])
print(best)