\(i\ (1\le i\le N)\) に対して、番号が \(i\) であるスマートフォンに対して通知が来る回数を \(C _ i\) とします。 この \(C _ i\) が得られれば、答えを \(\max\lbrace0,S _ i-C _ i\rbrace\) として求めることができます。

imos 法を用いることで、\(C _ i\) の値を高速に計算することができます。 具体的には、次のようなアルゴリズムによって計算することができます。

• はじめ、長さ \(N\) の整数列 \(A\) を \((0,0,\ldots,0)\) で初期化する。
• \(i=1,2,\ldots,Q\) に対して、次の操作を行う。
  • \(A _ {L _ i}\) を \(1\) 増やす。
  • \(R _ i+1\le N\) なら、\(A _ {R _ i+1}\) を \(1\) 減らす。
• \(A\) の累積和 \(C _ i=A _ 1+A _ 2+\cdots+A _ i\) が求めるものである。

時間計算量は \(O(N+Q)\) となります。

実装は以下のようになります。

#include <iostream>
#include <vector>

int main() {
    using namespace std;
    int N, Q;
    cin >> N >> Q;

    vector<int> S(N);
    for (int& s : S) {
        cin >> s;
    }

    // imos 法で C[i] を求める
    vector<int> C(N + 1);
    for (int i = 0; i < Q; ++i) {
        int L, R;
        cin >> L >> R;
        ++C[L - 1]; // 0-indexed に直して操作することに注意
        --C[R];
    }
    C.pop_back();

    // 累積和を取る
    for (int i = 1; i < N; ++i) {
        C[i] += C[i - 1];
    }

    for (int i = 0; i < N; ++i) {
        cout << S[i] - min(S[i], C[i]) << " "; // max(0, S[i] - C[i]) が答え
    }
    cout << endl;
    return 0;
}

N, Q = map(int, input().split())

S = list(map(int, input().split()))

# imos 法で C[i] を求める
C = [0 for _ in range(N + 1)]
for i in range(Q):
    L, R = map(int, input().split())
    C[L - 1] += 1 # 0-indexed に直して操作することに注意
    C[R] -= 1
C = C[:-1]

# 累積和を取る
for i in range(1, N):
    C[i] += C[i - 1]

for i in range(N):
    print(S[i] - min(S[i], C[i]), end=' ') # max(0, S[i] - C[i]) が答え
print('')