1. Идея

Нужно выполнить k операций вида: прибавить число x ко всем элементам на отрезке [l, r], а потом ответить на q запросов суммы на отрезке [L, R].

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

Главная идея состоит из двух шагов:

1. Сначала быстро применить все диапазонные прибавления с помощью разностного массива.
2. Затем по полученному массиву количеств воды построить префиксные суммы, чтобы быстро отвечать на запросы суммы на отрезке.

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

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

Пусть есть массив a[1..n]. Чтобы прибавить x ко всем элементам на отрезке [l, r], можно не менять все элементы сразу, а использовать разностный массив d.

Для операции [l, r] += x достаточно сделать:

• d[l] += x
• d[r + 1] -= x

Тогда после восстановления массива префиксными суммами получится, что:

• начиная с позиции l значение увеличится на x,
• после позиции r это увеличение отменится.

То есть все k команд можно записать в d за O(k).

Наблюдение 2. Как восстановить итоговый массив

Если d — разностный массив, то итоговое количество воды на грядке i равно:

• a[i] = a[i - 1] + d[i]

Так мы за один проход получаем весь массив a[1..n].

Наблюдение 3. Как быстро отвечать на суммы на отрезке

После того как известен массив a, нужно много раз находить сумму на отрезке [L, R].

Для этого строим массив префиксных сумм pref:

• pref[i] = pref[i - 1] + a[i]

Тогда ответ на запрос:

• сумма на [L, R] равна pref[R] - pref[L - 1]

Каждый запрос обрабатывается за O(1).

3. Алгоритм

1. Считать n, k, q.
2. Создать разностный массив d размера n + 3, заполненный нулями.
3. Для каждой из k команд:
   • считать l, r, x,
   • сделать d[l] += x,
   • сделать d[r + 1] -= x.
4. Создать массивы a и pref размера n + 1.
5. Для i от 1 до n:
   • восстановить значение на грядке: a[i] = a[i - 1] + d[i],
   • посчитать префиксную сумму: pref[i] = pref[i - 1] + a[i].
6. Для каждого из q запросов:
   • считать L, R,
   • вывести pref[R] - pref[L - 1].

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

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

Шаг 1. Корректность разностного массива

Рассмотрим одну команду: прибавить x ко всем грядкам от l до r.

После операций:

• d[l] += x
• d[r + 1] -= x

при переходе к префиксным суммам:

• для позиций меньше l эта прибавка не влияет,
• начиная с l в накопленной сумме появляется +x,
• после r прибавка компенсируется значением -x в d[r + 1].

Значит, ровно на отрезке [l, r] все элементы увеличиваются на x.

Если таких команд несколько, их влияние просто складывается, потому что все изменения линейны: вклады всех операций суммируются.

Следовательно, после восстановления массива a каждая грядка содержит ровно итоговое количество воды после всех команд.

Шаг 2. Корректность префиксных сумм

По определению:

• pref[i] — это сумма элементов a[1] + a[2] + ... + a[i].

Тогда сумма на отрезке [L, R] равна:

• сумма от 1 до R,
• минус сумма от 1 до L - 1.

То есть ответ равен pref[R] - pref[L - 1].

Таким образом, алгоритм правильно отвечает на каждый запрос.

5. Сложность

• Обработка всех k команд: O(k)
• Восстановление массива и построение префиксных сумм: O(n)
• Ответы на все q запросов: O(q)

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

• O(n + k + q)

Память:

• O(n)

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

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

    vector<long long> d(n + 3, 0);

    for (int i = 0; i < k; i++) {
        int l, r;
        long long x;
        cin >> l >> r >> x;
        d[l] += x;
        d[r + 1] -= x;
    }

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

    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + d[i];
        pref[i] = pref[i - 1] + a[i];
    }

    for (int i = 0; i < q; i++) {
        int L, R;
        cin >> L >> R;
        cout << pref[R] - pref[L - 1] << '\n';
    }

    return 0;
}

7. Код на Python 3

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

d = [0] * (n + 3)

for _ in range(k):
    l, r, x = map(int, input().split())
    d[l] += x
    d[r + 1] -= x

a = [0] * (n + 1)
pref = [0] * (n + 1)

for i in range(1, n + 1):
    a[i] = a[i - 1] + d[i]
    pref[i] = pref[i - 1] + a[i]

for _ in range(q):
    L, R = map(int, input().split())
    print(pref[R] - pref[L - 1])