この問題におけるシャンパンタワーでは、上のグラスから順番に、満杯になるまでシャンパンが注がれていくと考えることができます。 これは、次のような一つの容器にシャンパンを注ぎ、下から各グラスが担当する領域がある状況に対応させることができます。

この言い換えができれば、各グラスが担当する領域を求め、今どれだけのシャンパンが注がれているかを管理することでこの問題を \(O(N+Q)\) 時間で解くことができます。

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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long> C(N);
    for (long& c : C) {
        cin >> c;
    }

    // それぞれのグラスが担当する領域が [C[i], C[i+1]) になるようにする
    C.emplace(begin(C)); // 先頭に 0 を追加して
    for (int i = 0; i < N; ++i) {
        C[i + 1] += C[i]; // 累積和を求める
    }

    long now_champagne = 0; // 現在注がれているシャンパンの総量
    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 1) { // 注ぐなら
            int V;
            cin >> V;
            now_champagne += V; // 容量を足す
        } else { // 問い合わせなら
            int k;
            cin >> k;
            --k; // 0-indexed にして
            // 担当する領域に含まれるシャンパンの量を求める
            cout << min(C[k + 1], now_champagne) - min(C[k], now_champagne) << endl;
        }
    }
    return 0;
}

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

C = [0] + list(map(int, input().split()))

# それぞれのグラスが担当する領域が [C[i], C[i+1]) になるようにする
for i in range(N):
    C[i + 1] += C[i] # 累積和を求める

now_champagne = 0 # 現在注がれているシャンパンの総量
for i in range(Q):
    t, v = map(int, input().split())
    if t == 1: # 注ぐなら
        now_champagne += v # 容量を足す
    else: # 問い合わせなら
        v -= 1 # 0-indexed にして
        # 担当する領域に含まれるシャンパンの量を求める
        print(min(C[v + 1], now_champagne) - min(C[v], now_champagne))