この問題は、次のような \(3\) 種類の問題を高速に処理することができれば解くことができます。

問題 1

長さ \(N\) の列 \(V=(V _ 1,V _ 2,\ldots,V _ N)\) に対して、次の \(2\) 種類のクエリを処理せよ。

• 整数組 \((l,r)\ (1\le l\le r\le N)\) および整数 \(x\) が与えられる。\(V _ l,V _ {l+1},\ldots,V _ r\) すべてに \(x\) を加える。
• 整数 \(p\ (1\le p\le N)\) が与えられる。\(V _ p\) の値を求める。

問題 2

長さ \(N\) の列 \(O=(1,1,\ldots,1)\) に対して、次の \(2\) 種類のクエリを処理せよ。

• 整数 \(p\ (1\le p\le N)\) が与えられる。\(O _ p\leftarrow0\) と更新する。
• 整数 \(k\ (1\le k\le O _ 1+O _ 2+\cdots+O _ N)\) が与えられる。\(O _ 1+O _ 2+\cdots+O _ j=k\) となるような最小の整数 \(j\) を求める。

問題 3

長さ \(N\) の列 \(S=(0,0,\ldots,0)\) に対して、次の \(2\) 種類のクエリを処理せよ。

• 整数 \(p\ (1\le p\le N)\) および整数 \(v\) が与えられる。\(S _ p\leftarrow v\) と更新する。
• 整数 \(j\ (1\le j\le N)\) が与えられる。\(S _ 1+S _ 2+\cdots+S _ j\) の値を求める。

具体的には、操作 \(1\) には問題 1 の \(1\) 番目のクエリを、操作 \(2\) には問題 1 の \(2\) 番目のクエリと問題 2 の \(1\) 番目のクエリと問題 3 の \(1\) 番目のクエリを、操作 \(3\) には問題 2 の \(2\) 番目のクエリと問題 3 の \(2\) 番目のクエリを行うことでこの問題を解くことができます。

多くの操作は Binary Indexed Tree（フェニック木）の基本的な操作で行うことができます。 問題 1 については累積和をとると \(V\) と一致するような列を管理することで、問題 2 の \(2\) 番目のクエリは BIT 上の二分探索を利用することなどで高速に処理することができます。

実装例は以下のようになります。 以下の実装例では、AtCoder Library で提供されているセグメント木上の二分探索を利用するため、列 \(O\) はセグメント木を使って管理しています。

#include <iostream>
#include <atcoder/segtree>
#include <atcoder/fenwicktree>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;

    atcoder::fenwick_tree<long> open(N + 1), closed(N);
    atcoder::segtree<int, plus{}, []{return 0;}> is_open(vector(N, 1));

    for (int i = 0, p = 0; i < N; ++i) {
        int V;
        cin >> V;
        open.add(i, V - p); // V の差分を管理する
        p = V;
    }

    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            --l; // 0-indexed 右半開区間にして
            open.add(l, x); // 左に +x
            open.add(r, -x); // 右に -x
        } else if (t == 2) {
            int p;
            cin >> p;
            --p;
            is_open.set(p, 0); // 閉店して
            closed.add(p, open.sum(0, p + 1)); // 売上記録を更新
        } else {
            int k;
            cin >> k;
            int j = is_open.max_right(0, [k](int r){return r < k;}); // 二分探索をして
            cout << closed.sum(0, j) << endl; // 売上記録の合計を出力
        }
    }
    return 0;
}

from atcoder.segtree import SegTree
from atcoder.fenwicktree import FenwickTree


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

open = FenwickTree(N + 1)
closed = FenwickTree(N)

is_open = SegTree(lambda a, b: a + b, 0, [1 for i in range(N)])

p = 0
for i, V in enumerate(map(int, input().split())):
    open.add(i, V - p) # V の差分を管理する
    p = V

for i in range(Q):
    t, *q = map(int, input().split())

    if t == 1:
        l, r, x = q
        l -= 1 # 0-indexed 右半開区間にして
        open.add(l, x) # 左に +x
        open.add(r, -x) # 右に -x
    elif t == 2:
        p = q[0]
        p -= 1
        is_open.set(p, 0) # 閉店して
        closed.add(p, open.sum(0, p + 1)) # 売上記録を更新
    else:
        k = q[0]
        j = is_open.max_right(0, lambda r: r < k) # 二分探索をして
        print(closed.sum(0, j)) # 売上記録の合計を出力