Treap 40pts求调

#include <bits/stdc++.h>
template <class T = int, T error = 0>
class Treap {
private:
	struct node {
		node* ch[2];
		int r, s, cnt;
		T v;
		int cmp(T x) {
			if (x == v) return -1;
			return x < v ? 0 : 1;
		}
		void maintain() {
			s = (ch[0] == nullptr ? 0 : ch[0] -> s ) + (ch[1] == nullptr ? 0 : ch[1] -> s ) + cnt;
		}
	};
	void rotate(node* &o, int d) {
		node* k = o -> ch[d ^ 1]; o -> ch[d ^ 1] = k -> ch[d]; k -> ch[d] = o;
		o -> maintain(); k -> maintain(); o = k;
	}
public:
	node* root = nullptr;
	void insert(node* &o, T x) {
		if (o == nullptr) {
			o = new node(); o -> cnt = 1; o -> ch[0] = o -> ch[1] = nullptr; o -> v = x; o -> r = rand();
		}
		else {
			int d = o -> cmp(x);
			if (d == -1) o -> cnt ++;
			else {
				insert(o -> ch[d], x);
				if (o -> ch[d] -> r > o -> r) rotate(o, d ^ 1);
			}
		}
        o -> maintain();
	}
	void remove(node* &o, T x) {
        if (o == nullptr) return;
		int d = o -> cmp(x);
		if (d == -1) {
			if (o -> cnt > 1) o -> cnt --;
			else if (o -> ch[0] == nullptr) o = o -> ch[1];
			else if (o -> ch[1] == nullptr) o = o -> ch[0];
			else {
				int d2 = (o -> ch[0] > o -> ch[1] ? 1 : 0);
				rotate(o, d2); remove(o -> ch[d2], x);
			}
		}
		else remove(o -> ch[d], x);
		if (o != nullptr) o -> maintain();
	}
	node* find(node* o, T x) {
		while (o != nullptr) {
			int d = o -> cmp(x);
			if (d == -1) return o;
			else o = o -> ch[d];
		}
		return nullptr;
	}
    T kthGreatest(node* o, int k) {
		if (o == nullptr || k <= 0 || k > o -> s) return error;
		int s = (o -> ch[1] == nullptr ? 0 : o -> ch[1] -> s);
		if (k >= s + 1 && k <= s + o -> cnt) return o -> v;
		else if (k <= s) return kthGreatest(o -> ch[1], k);
		else return kthGreatest(o -> ch[0], k - s - o -> cnt);
	}
	T kthLeast(node* o, int k) {
		if (o == nullptr || k <= 0 || k > o -> s) return error;
		int s = (o -> ch[0] == nullptr ? 0 : o -> ch[0] -> s);
		if (k >= s + 1 && k <= s + o -> cnt) return o -> v;
		else if (k <= s) return kthLeast(o -> ch[0], k);
		else return kthLeast(o -> ch[1], k - s - o -> cnt);
	}
    int rankGreatest(node* o, T k) {
		if (o == nullptr) return 1;
		int s = (o -> ch[1] == nullptr ? 0 : o -> ch[1] -> s);
		if (o -> v == k) return s + 1;
		if (o -> v > k) return s + o -> cnt + rankGreatest(o -> ch[0], k);
		return rankGreatest(o -> ch[1], k);
	}
	int rankLeast(node* o, T k) {
		if (o == nullptr) return 1;
		int s = (o -> ch[0] == nullptr ? 0 : o -> ch[0] -> s);
		if (o -> v == k) return s + 1;
		if (o -> v < k) return s + o -> cnt + rankLeast(o -> ch[1], k);
		return rankLeast(o -> ch[0], k);
	}
	T pre(node *o, T k) {
		int p = error;
		while (o != nullptr) {
			int d = o -> cmp(k);
			if (d == 0 || d == -1) o = o -> ch[0];
			else { p = o -> v; o = o -> ch[1]; }
		}
		return p;
	}
	T post(node *o, T k) {
		int p = error;
		while (o != nullptr) {
			int d = o -> cmp(k);
			if (d == 1 || d == -1) o = o -> ch[1];
			else { p = o -> v; o = o -> ch[0]; }
		}
		return p;
	}
};
Treap<int, -1> t;
#define rs (t.root == nullptr ? 0 : t.root -> s)
int main() {
	// freopen("a.txt", "r", stdin);
    int delta = 0, low;
    int n, ans = 0;
    std :: cin >> n >> low;
    while (n --) {
        char opt; int k;
        std :: cin >> opt >> k;
        if (opt == 'I') {
		if (k - delta >= low) {
        		t.insert(t.root, k - delta);
        	} 
			else ans ++;
		}
        if (opt == 'A') { delta += k; low -= k; }
        if (opt == 'S') {
        	delta -= k; low += k;
			ans += rs;
        	while (t.pre(t.root, low) != -1) t.remove(t.root, t.pre(t.root, low));
			ans -= rs;
        }
        if (opt == 'F') {
        	if (rs >= k) std :: cout << t.kthGreatest(t.root, k) + delta << '\n';
        	else puts("-1");
        }
    }
    std::cout << ans << '\n';
    return 0;
}