Splay求条

#include<bits/stdc++.h>
using namespace std;
const int N = 1100010,INF = (1<<30)+1;
int ch[N][2],cnt[N],siz[N],val[N],fa[N],tot,root,minn;
void pushup(int u){siz[u] = siz[ch[u][0]]+siz[ch[u][1]]+cnt[u];}
void rotate(int x){
	int y = fa[x],z = fa[y];
	int k = (ch[y][1]==x);
	ch[y][k] = ch[x][k^1],fa[ch[x][k^1]] = y;
	ch[x][k^1] = y,fa[y] = x;
	ch[z][ch[z][1]==y] = x,fa[x] = z;
	pushup(y);
	pushup(x);
}
void splay(int x,int k){
	int y,z;
	while(fa[x]!=k){
		y = fa[x],z = fa[y];
		if(z!=k)(ch[y][0]==x)^(ch[z][0]==y)?rotate(x):rotate(y);
		rotate(x);
	}
	if(!k)root = x;
}
void find1(int v){
	int x = root;
	while(ch[x][v>val[x]]&&val[x]!=v)x = ch[x][v>val[x]];
	splay(x,0);
}
int getpre(int v){
	find1(v);
	int x = root;
	if(val[x]<v)return x;
	x = ch[x][0];
	while(ch[x][1])x = ch[x][1];
	splay(x,0);
	return x;
}
int getsuc(int v){
	find1(v);
	int x = root;
	if(val[x]>v)return x;
	x = ch[x][1];
	while(ch[x][0])x = ch[x][0];
	splay(x,0);
	return x;
}
void del(int v){
	int p = getpre(v),s = getsuc(v);
	splay(p,0);
	splay(s,p);
	int d = ch[s][0];
	if(cnt[d]>1){
		cnt[d]--;
		splay(d,0);
	}
	else{
		ch[s][0] = 0;
		splay(s,0);
	}
}
void insert(int v){
	int x = root,p = 0;
	while(x&&val[x]!=v)p = x,x = ch[x][v>val[x]];
	if(x)cnt[x]++;
	else{
		x = ++tot;
		ch[p][v>val[p]] = x;
		fa[x] = p;
		val[x] = v;
		cnt[x] = siz[x] = 1;
	}
	splay(x,0);
}
int getrank(int v){
	insert(v);
	int ans = siz[ch[root][0]];
	del(v);
	return ans;
}
int getval(int k){
	int x = root,y;
	while(1){
		y = ch[x][1];
		if(k<=siz[y]&&y)x = y;
		else if(k<=siz[y]+cnt[x])break;
		else k = k-siz[y]-cnt[x],x = ch[x][0];
	}
	splay(x,0);
	return val[x];
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	insert(INF);
	int n,x,ans = 0;
	char op;
	cin>>n>>minn;
	for(int i = 1;i<=n;i++){
		cin>>op;
		cin>>x;
		if(op=='I'&&x>=minn)insert(x);
		else if(op=='A')for(int i = 1;i<=tot;i++)val[i]+=x;
		else if(op=='S'){
			int s = getsuc(x+minn-1);
			splay(s,0);
			ans+=siz[ch[root][0]];
			ch[root][0] = 0;
			siz[root]-=siz[ch[root][0]];
			for(int i = 1;i<=tot;i++)val[i]-=x;
		}
		else {
			if(x>=siz[root])cout<<-1<<'\n';
			else cout<<getval(x+1)<<'\n';
		}
	}
	cout<<ans;
	return 0;
}