単純な解法として \(M\) 回の作業で毎回区画 \(L_j\) から区画 \(R_j\) までを確認するという方法がありますが、時間計算量 \(\mathrm{O}(NM)\) となってしまい、実行時間制限に間に合うことは難しいです。

そこで、収穫作業を毎度行うのではなく、区画 \(L_j\) から区画 \(R_j\) までに印をつけて、最後に区画 \(1\) から \(N\) について印がついている区画を収穫するという方法でも同じ答えが得られます。

この印をつけるという操作を最初は全て \(0\) で初期化された配列 \(B\) について\(B_{L_j},B_{L_j+1},\ldots,B_{R_j}\) にそれぞれ \(1\) 加算するという操作に言い換えることができます。また、この言い換え後の操作は imos 法を用いることで最後に全ての印をつける操作をまとめて行えます。

よって、時間計算量 \(\mathrm{O}(N+M)\) で解くことができました。

実装例(C++)

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