クエリを処理する中で、\(A\) の長さは最大で \(2 \times 10^{14}\) になります。そのため、\(A\) をそのまま配列として保持することは難しいです。

ここで追加クエリごとの \((c,x)\) の組を列として保持することで \(A\) を管理する方法があります。あるいは、\(A\) を連長圧縮(ランレングス圧縮)をした列で管理すると考えても良いです。

\(A\) に対して削除クエリを行う方法を考えます。\(A\) の先頭から順に \((c,x)\) の組を見ていき、\(c \leq k\) の時は整数の削除し再び先頭から削除する操作を続け、\( c > k\) の時は先頭の整数の組を \((c-k,x)\) に置き換え削除をやめます。

この操作を通して整数 \(x\) を \(i\) 個削除した情報を得られるため、容易に削除した数の総和を求めることができます。

追加クエリでは整数の組は \(1\) 個追加され、一連削除クエリでは高々追加された整数の組の数しか削除せず、各クエリでは高々 \(1\) つの整数の組に対して変更の操作を行います。そのため、時間計算量 \(\mathrm{O}(Q)\) で解くことができました。

出力する整数の最大値は \(10^{18}\) と 32 bit整数型ではオーバーフローしてしまうため実装の際は注意する必要があります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int q;
    cin >> q;
    // 追加クエリを順に que で管理する
    queue<pair<ll, ll>> que;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            ll c, x;
            cin >> c >> x;
            que.emplace(c, x); // (c,x) を追加
        } else {
            ll k;
            cin >> k;
            ll ans = 0;
            // 先頭から (c,x) を順に見ていく。
            while (!que.empty() && que.front().first <= k) {
                // 先頭を削除し和を加算する
                ans += que.front().first * que.front().second;
                k -= que.front().first;
                que.pop();
            }
            if (k != 0) {
                // 先頭の(c,x)について c>k なので (c-k,x)で置き換える
                que.front().first -= k;
                ans += k * que.front().second;
            }
            cout << ans << '\n';
        }
    }
}