最初に与えられる \(A\) で花壇の水分を管理するとします。 この問題では \(M\) 回の作業すべてについて、\(j\) 回目の操作で \(i=L_j,\ldots,R_j\) で \(A_i \leftarrow A_i+D_j\) と更新すれば答えを求められます。 ですが、この解法は \(\Theta (NM)\) で実行時間制限には間に合うことは難しいです。

今回は最後の \(A\) の状態のみが効かれているため、ここで imos法 を用いることで時間計算量が \(\mathrm{O}(N+M)\) にすることができます。

具体的には、\(A\) とは別に増分を管理する配列 \(S\) を作り、\(j\) 回目の操作では \(S_{L_j} \leftarrow S_{L_j}+D_j\), \(S_{R_j+1} \leftarrow S_{R_j+1} -D_j\) と更新して最後に、\(i=2,3,\ldots,N\) の順に \(S_{i} \leftarrow S_{i}+S_{i-1}\) と更新すると、\(A_i+S_i\) が最終的な答えとなります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (auto& e : a) cin >> e;
    vector<long long> sum(n + 1);
    for (int i = 0; i < m;++i){
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        sum[l] += d, sum[r] -= d;
    }
    for (int i = 0; i < n; ++i) sum[i + 1] += sum[i];
    for (int i = 0; i < n; ++i) a[i] += sum[i];
    for (int i = 0; i < n; ++i) cout << a[i] << " \n"[i == n - 1];
}