如题

#include<bits/stdc++.h>
using namespace std;
mt19937 mt(chrono::system_clock::to_time_t(chrono::system_clock::now()));

struct node
{
	int lc,rc,val,siz,cnt,w;
}tree[100001];

int root,len;

int newnode(int v)
{
	tree[++len]={0,0,v,1,1,(int)mt()};
	return len;
}

void pushup(int x)
{
	tree[x].siz=tree[tree[x].lc].siz+tree[tree[x].rc].siz+tree[x].cnt;
}

void zig(int &id)
{
	int tmp=tree[id].lc;
	tree[id].lc=tree[tmp].rc;
	tree[tmp].rc=id;
	tree[tmp].siz=tree[id].siz;
	pushup(id);
	id=tmp;
}

void zag(int &id)
{
	int tmp=tree[id].rc;
	tree[id].rc=tree[tmp].lc;
	tree[tmp].lc=id;
	tree[tmp].siz=tree[id].siz;
	pushup(id);
	id=tmp;
}

void insert(int &id,int val)
{
	if(!id)
	{
		id=newnode(val);
		return;
	}
	tree[id].siz++;
	if(tree[id].val>val)
	{
		insert(tree[id].lc,val);
		if(tree[tree[id].lc].w>tree[id].w)
			zig(id);
	}
	else if(tree[id].val<val)
	{
		insert(tree[id].rc,val);
		if(tree[tree[id].rc].w>tree[id].w)
			zag(id);
	}
	else tree[id].cnt++;
}

void erase(int &id,int val)
{
	if(!id)
		return;
	if(tree[id].val==val)
	{
		if(tree[id].cnt>1)
		{
			tree[id].cnt--;
			pushup(id);
			return;
		}
		else
		{
			if(!tree[id].lc||!tree[id].rc)
				id=tree[id].lc+tree[id].rc;
			else if(tree[tree[id].lc].w>tree[tree[id].rc].w)
			{
				zig(id);
				erase(tree[id].rc,val);
			}
			else
			{
				zag(id);
				erase(tree[id].lc,val);
			}
		}
	}
	else if(tree[id].val>val)
		erase(tree[id].lc,val);
	else erase(tree[id].rc,val);
	pushup(id);
}

int rnk(int id,int val)
{
	if(!id)
		return 1;
	if(tree[id].val>val)
		return rnk(tree[id].lc,val);
	if(tree[id].val<val)
		return rnk(tree[id].rc,val)+tree[id].siz-tree[tree[id].rc].siz;
	return tree[tree[id].lc].siz+1;
}

int kth(int id,int k)
{
	if(!id)
		return -1;
	if(k<=tree[tree[id].lc].siz)
		return kth(tree[id].lc,k);
	else if(k<=tree[tree[id].lc].siz+tree[id].cnt)
		return tree[id].val;
	return kth(tree[id].rc,k-tree[id].siz+tree[tree[id].rc].siz);
}

int pre(int val)
{
	int rk=rnk(root,val);
	if(rk==1)
		return -1e9;
	return kth(root,rk-1);
}

int nxt(int val)
{
	int tmp=kth(root,rnk(root,val+1));
	if(tmp==-1)
		return 1e9;
	return tmp;
}
//这前面都是平衡树，模板题是过了的
int main()
{
	int n,minn,sum=0;
	int tot=0,del=0;//统计增加人数和退出人数
	cin>>n>>minn;
	for(int i=1;i<=n;i++)
	{
		char opt;
		int k;
		cin>>opt>>k;
		if(opt=='I')
		{
			if(k-sum>=minn)
			{
				insert(root,k-sum);
				tot++;
			}
		}
		if(opt=='A')
		{
			sum+=k;
		}
		if(opt=='S')
		{
			sum-=k;
			insert(root,minn-sum);//加一个虚拟的节点，然后把这个节点的所有前驱全部删掉
			while(pre(minn-sum)!=-1e9)
			{
				erase(root,pre(minn-sum));
				del++;
			}
			erase(root,minn-sum);//再把自己删掉
		}
		if(opt=='F')
		{
			if(k>tot-del)//没这么多人就输出-1
				cout<<"-1\n";
			else
			{
				cout<<kth(root,tot-del-k+1)+sum<<endl;//查询第k大
			}
		}
	}
	cout<<del<<endl;
}