数列 \((A_1,\ldots ,A_N)\) を \(i\) 回目の操作が操作 \(2\) ならば \(A_i=X_i\) そうでないならば \(0\) で定めます。このとき \(K+1\) 回目の操作の直前において袋に入っているそれぞれボールに書かれた数は \(X_i+A_{i+1}+\cdots A_K\) と書けます。また、累積和の考え方を使うと、 \(S_i\) を \(S_i=A_1+\cdots A_i\) で定めて、これを \(X_i+(S_K-S_i)=(X_i-S_i)+S_K\) と書く事が出来ます。ここで \((A_i)\) および \((S_i)\) は順に見ていく事で簡単に計算ができます。

さて、最小の番号のボールを取り出そうとしたとき 、 \(S_K\) の部分についてはボールによらないので、残っているボールの中で \(X_i-S_i\) が最も小さいものを取り出せば良い事が分かります。 よって、操作 \(1\) の度に \(X_i\) ではなく \(X_i-S_i\) の書かれたボールを入れていることにすれば、操作 \(1\) と操作 \(3\) のみの場合に帰着する事が出来ます。（ただし、出力する際には \(S_K\) を足すことを忘れないようにしてください。）

これは優先度付きキューなどのデータ構造を用いることによって高速に、具体的には \(O(Q\log Q)\) で解くことができます。よってこの問題を解く事が出来ました。

C++による実装例:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	priority_queue<ll, vector<ll>, greater<ll> >pq;
	int q, p;
	ll x;
	ll sum = 0;
	cin >> q;
	rep(qq, q) {
		cin >> p;
		if (p == 1) {
			cin >> x;
			pq.push(x - sum);
		}
		else if (p == 2) {
			cin >> x;
			sum += x;
		}
		else if (p == 3) {
			x = pq.top();
			cout << x + sum << endl;
			pq.pop();
		}
	}
	return 0;
}