代码内含调试操作

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const long long INF = 0x7fffffff;
char ch;
int n, m, x, root = 1, ct = 0, s = 0, go = 0;
struct tree
{
	int l, r, cnt, siz, rank;
	long long val;
} tr[N];

void pushup(int u) {tr[u].siz = tr[tr[u].l].siz + tr[tr[u].r].siz + tr[u].cnt;}
int gettree(int x)
{
	int u = ++ ct;
	tr[u].val = x;
	tr[u].rank = rand();
	tr[u].l = tr[u].r = 0;
	tr[u].cnt = tr[u].siz = 1;
	cout << "ins " << u << ' ' << x << '\n' << '\n'; 
	return u;
}
void zig(int &u)
{
	int p = tr[u].l;
	tr[u].l = tr[p].r;
	tr[p].r = u, u = p;
	pushup(tr[u].r),pushup(u);
}
void zag(int &u)
{
	int p = tr[u].r;
	tr[u].r = tr[p].l;
	tr[p].l = u, u = p;
	pushup(tr[u].l), pushup(u);
}
void insert(int &u, int x)
{
	if(!u) u = gettree(x), s ++ ;
	else if(tr[u].val == x) tr[u].cnt ++ ;
	else if(tr[u].val > x)
	{
		insert(tr[u].l, x);
		if(tr[tr[u].l].rank > tr[u].rank) zig(u);
	}
	else
	{
		insert(tr[u].r, x);
		if(tr[tr[u].r].rank > tr[u].rank) zag(u);
	}
	pushup(u);
}
void del(int &u)
{
	if(tr[u].l || tr[u].r)
	{
		if(!tr[u].r || tr[tr[u].l].rank > tr[tr[u].r].rank) zig(u), del(tr[u].r);
		else zag(u), del(tr[u].l);
	}
	else u = 0;
	pushup(u);
}
void add(int u, int x)
{
    if(!u) return;
	if(tr[u].val != INF && tr[u].val != -INF)
    {
        tr[u].val += x;
	    cout << u << ' ' << tr[u].val;
	    if(tr[u].val < m) s -- , go ++ , del(u), cout << " ddd";
	    cout  << '\n';
    }
	add(tr[u].l, x);
	add(tr[u].r, x);
	pushup(u);
}
long long query(int u, int x)
{
	if(!u) return 0;
//	cout << u << ' ' << tr[u].val << '\n';
	if(tr[tr[u].l].siz >= x) return query(tr[u].l, x);
	else if(tr[tr[u].l].siz + tr[u].cnt >= x) return tr[u].val;
	else return query(tr[u].r, x - tr[tr[u].l].siz - tr[u].cnt);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	gettree(-INF), gettree(INF);
	while(n -- )
	{
		cin >> ch >> x;
		if(ch == 'I')
		{
			if(x >= m) insert(root, x);
			else go ++ ;
		}
		if(ch == 'A') add(root, x), cout << '\n';
		if(ch == 'S') add(root, -x), cout << '\n';
		if(ch == 'F')
		{
			if(x > s) cout << '\n' << -1 << '\n';
			else cout << '\n' << query(root, s - x + 2) << '\n';
		}
	}
	cout << go;
	return 0;
}