提交记录

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct fhq{
	int l,r,v,rd,size;
}tr[N];
int n,m,idx,root,ans,x,y,z,f[N];
mt19937 rnd(114);
int get_node(int v){
	tr[++idx].v=v;
	tr[idx].rd=rnd();
	tr[idx].size=1;
	return idx;
}
void push_up(int u){
	tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size+1;
}
void split(int now,int k,int &x,int &y){
	if(!now){
		x=y=0;
		return;
	}
	if(tr[now].v<=k){
		x=now;
		split(tr[now].r,k,tr[now].r,y);
	}
	else{
		y=now;
		split(tr[now].l,k,x,tr[now].l);
	}
	push_up(now);
}
int merge(int u,int v){
	if(!u||!v) return u|v;
	if(tr[u].rd<tr[v].rd){
		tr[u].r=merge(tr[u].r,v);
		push_up(u);
		return u;
	}
	else{
		tr[v].l=merge(u,tr[u].l);
		push_up(v);
		return v;
	}
}
void insert(int v){
	split(root,v,x,y);
	root=merge(merge(x,get_node(v)),y);
}
void del(int v){
	split(root,v,x,z),split(x,v-1,x,y);
	root=merge(x,z);
}
int kth(int k){
	int u=root;
	if(k>tr[u].size) return -1;
	while(114514){
		if(k<=tr[tr[u].r].size) u=tr[u].r;
		else if(k>tr[tr[u].r].size+1) k-=tr[tr[u].r].size+1,u=tr[u].l;
		else return tr[u].v;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		char opt;
		int c;
		cin>>opt>>c;
		if(opt=='I'){
			if(c>=m) insert(c);
		}
		if(opt=='A') {
			for(int i=1;i<=idx;i++){
				tr[i].v+=c;
			}
		}
		if(opt=='S'){
			for(int i=1;i<=idx;i++){
				tr[i].v-=c;
				if(tr[i].v<m&&!f[i]){
					f[i]=1;
					del(tr[i].v);
					ans++;
				}
			}
		}
		if(opt=='F'){
			cout<<kth(c)<<endl;
		}
	}
	cout<<ans;
	return 0;
}