Point Add and Array Add [yukicoder 1000]

https://yukicoder.me/problems/no/1000

前提知識

• 遅延セグメントツリー（区間add, 1点取得）
• クエリ先読み

解説

https://yukicoder.me/submissions/436489

配列のある区間をコピーしてaddするようなデータ構造は持っていない。
どこから手を付けようか。

まずは簡単な場合から考えてみる。
Bに値が足されるのはクエリBであるため、クエリBだけで構成された場合を考えてみる。
例えば、n=5で、[2,4], [3,5], [1,4]というクエリBが来た場合、
それぞれの要素が足される回数のは、
1 2 3 3 1
となる。これは丁度、クエリBの区間について1を区間addすると得られる配列である。
足される回数が得られたら、要素の数とかけ合わせれば、数列Bが復元できる。
区間addするには遅延セグメントツリーを使うといい。
今回は、1点取得なので、BITを使うことでより高速に同様のことが行える。

さて、これでクエリBのみの場合は処理を行うことができた。
次にクエリAを処理しよう。
これはクエリ先読みテクを使うのだが、あるタイミングでクエリAが呼ばれたとする。
この時に要素x[i]に+y[i]される訳だが、この増分である、y[i]が要素x[i]に何回足されるかが分かれば、
クエリBのとき同様に掛け合わせて足すことで高速に計算できる。
これは、それ以降に呼ばれるクエリBの中で要素x[i]が何回含まれるかとなる。
最初にクエリ全体で各要素で含まれる回数を遅延セグメントツリーで計算しておき、
クエリを順番に見ていく過程で、クエリBが来たら、その区間の出現回数を-1すると、
常に「それ以降の各要素での呼ばれる回数」を表現する遅延セグメントツリーが作れる。

int N, Q, A[201010];
char C[201010]; int X[201010], Y[201010];
LazySegTree<ll, 1 << 18> cnt;
ll ans[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(q, 0, Q) cin >> C[q] >> X[q] >> Y[q];

    rep(q, 0, Q) if (C[q] == 'B') cnt.update(X[q] - 1, Y[q], 1);
    rep(i, 0, N) ans[i] = 1LL * A[i] * cnt.get(i, i + 1);

    rep(q, 0, Q) {
        if (C[q] == 'A') {
            int i = X[q] - 1;
            ans[i] += 1LL * Y[q] * cnt.get(i, i + 1);
        } else {
            cnt.update(X[q] - 1, Y[q], -1);
        }
    }

    rep(i, 0, N) {
        if(i) printf(" ");
        printf("%lld", ans[i]);
    }
    printf("\n");
}