Code

#include <iostream>
#define int long long
using namespace std;
const int maxn = 2e5;
const int N = maxn + 10;
int q[N << 1], _q[N << 1], t[N << 1];
int rd() {
	int res = 0; bool f = 0; char ch = getchar();
	while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
	return f ? -res : res;
}
void update(int x, int y) { while (x <= maxn) t[x] += y, x += x & -x; }
int query(int x) { int res = 0; while (x) res += t[x], x -= x & -x; return res; }
signed main() {
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int c = rd(), T = rd(), head = 1, tail = 0, _head = 1, _tail = 0;
	bool poo = false; int l, r;
	while (T --) {
		int opt = rd();
		if (opt == 1) {
			int x = rd();
			q[++ tail] = x, update(tail, x);
			while (_head <= _tail && q[_q[_tail]] <= x) -- _tail;
			_q[++ _tail] = tail;
		}
		else if (opt == 2) {
			int y = rd();
			if (poo && r - l + 1 > y) l += y;
			else if (poo && r - l + 1 == y) poo = false;
			else {
				if (poo) y -= r - l + 1;
				while (y >= q[head]) {
					if (_head <= _tail && _q[_head] == head) ++ _head;
					y -= q[head], update(head, -q[head]), ++ head;
				}
				if (y) {
					if (_head <= _tail && _q[_head] == head) ++ _head;
					l = y + 1, r = q[head], update(head, -q[head]), ++ head, poo = true;
				}
				else poo = false;
			}
		} else if (opt == 3) {
			int z = rd();
			if (poo && r - l + 1 >= z) printf("%lld\n", l + z - 1);
			else {
				if (poo) z -= r - l + 1;
				int _l = head, _r = tail, ans;
				while (_l <= _r) {
					int mid = _l + _r >> 1;
					if (query(mid) >= z) ans = mid, _r = mid - 1;
					else _l = mid + 1;
				}
				printf("%lld\n", z - query(ans - 1));
			}
		} else {
			printf("%lld\n", max((poo ? r : 0ll), (_head <= _tail ? q[_q[_head]] : 0ll)));
		}
	}
	return 0;
}

用树状数组和单调队列分别维护问题3和问题4。