1. Идея

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

Нужен способ делать прибавление на отрезке за O(1).

Для этого используется разностный массив:

• в позиции l записываем начало прибавки: +v
• в позиции r + 1 записываем конец прибавки: -v

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

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

Пусть есть массив итоговых надбавок a.

Если на всём отрезке [l; r] нужно прибавить v, то это означает:

• начиная с позиции l, все значения становятся на v больше
• начиная с позиции r + 1, это увеличение должно прекратиться

Именно это и хранит разностный массив diff:

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

Тогда при накоплении суммы:

• до l прибавка ещё не действует
• на отрезке от l до r действует +v
• после r действие отменяется

Важно, что несколько распоряжений просто суммируются друг с другом.

3. Алгоритм

1. Считываем n и m.
2. Создаём массив diff размера n + 2, заполненный нулями.
   • размер n + 2 нужен, чтобы безопасно обращаться к diff[r + 1], даже если r = n
3. Для каждого из m распоряжений:
   • считываем l, r, v
   • делаем diff[l] += v
   • делаем diff[r + 1] -= v
4. Восстанавливаем итоговый массив:
   • заводим переменную cur = 0
   • идём по позициям от 1 до n
   • прибавляем diff[i] к cur
   • текущее значение cur и есть итоговая надбавка в позиции i
5. Выводим все n значений.

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

Докажем, почему после всех операций префиксная сумма массива diff даёт правильный ответ.

Рассмотрим одно распоряжение l, r, v.

После выполнения:

• diff[l] увеличилось на v
• diff[r + 1] уменьшилось на v

Что произойдёт при подсчёте префиксной суммы?

• для позиций i < l это распоряжение ещё не попадает в сумму, значит вклад равен 0
• для позиций l <= i <= r в префиксную сумму уже вошло +v, но ещё не вошло -v, значит вклад равен v
• для позиций i > r в сумму вошли и +v, и -v, они сократились, значит вклад снова 0

То есть одно распоряжение даёт ровно нужное прибавление на отрезке [l; r] и нигде больше.

Так как все распоряжения независимы, их вклады просто складываются. Значит, после обработки всех запросов префиксная сумма массива diff в каждой позиции даёт точную итоговую надбавку.

5. Сложность

• Обработка всех распоряжений: O(m)
• Восстановление ответа: O(n)

Итоговая сложность: O(n + m)

Память: O(n)

Такое решение проходит при ограничениях до 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

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

    for (int i = 0; i < m; i++) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        diff[l] += v;
        diff[r + 1] -= v;
    }

    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        if (i > 1) {
            cout << ' ';
        }
        cout << cur;
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

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

diff = [0] * (n + 2)

for _ in range(m):
    l, r, v = map(int, input().split())
    diff[l] += v
    diff[r + 1] -= v

cur = 0
ans = []

for i in range(1, n + 1):
    cur += diff[i]
    ans.append(str(cur))

print(' '.join(ans))