Я знаю как решать эту задачу тремя способами, которые существенно отличаются друг от друга:

1. 2д дерево отрезков с проталкиванием, можно почитать здесь, я этого не писал, потому что скорее всего оно не зайдет из-за большой константы:)

2. Можно использовать дерево Фенвика, которое умеет прибавлять на отрезке, если почитаете здесь, то я думаю что напишете для одномерного массива, оно легко обобщается на 2д случай(то есть для прямоугольников), правда нужно будет уже 2^2=4 деревьев Фенвика, но зато просто пишется и быстро работает код

3. Есть еще одно решение, с использованием SQRT-декомпозиции по запросам: Вот предположим есть только запросы увеличения на прямоугольниках, их много, нужно как-то посчитать что получится в конце, можно сделать ее в оффлайне, то есть считать все запросы, а потом что-то сделать, пусть есть прямоугольник (x1, y1, x2, y2, v) нужно каждое число x1 <= x <= x2, y1 <= y <= y2 увеличить на v, как его посчитать в ответе, сделаем дополнительный массив inc, по которому в конце посчитаем частичные суммы, добавим inc[x1][y1] += v; inc[x2 + 1][y1] -= v; inc[x1][y2 + 1] -= v; inc[x2][y2] += v; Частичные суммы считаются за O(nm) если точка (x, y) не входит в прямоугольник (x1, y1, x2, y2) то в частичные суммы не посчитаем, иначе посчитаем, теперь когда мы умеем увеличивать на прямоугольнике в оффлайне, перейдем к решению задачи. Можно считывать запросы по K(выбираем k такое чтобы задача могла пройти:)) штук, и отвечать на каждый запрос за O(K), проходим по всех этих K запросах, если запрос найти сумму, то проходим по всем запросах увеличения, которые в этих K запросах и были раньше находим пересечение данного прямоугольника и того что был раньше, прибавляем к ответу площадь пересечения * на величину и еще прибавляем к ответу, то что в этом прямоугольнике и было раньше до текущих k запросов, на которую нужно было увеличить, и каждые K запросов Rebuildим суммы на прямоугольнике, это будет работать за O(nmq/k+qk), у меня в коде k — это MAGIC