传送门
平衡树简单题。
直接用fhgtreap实现分裂和合并就没了。
代码：
#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef pair<int,int> res;
int n,minn,cnt=0,rt=0,delta=0,son[N][2],siz[N],rd[N],val[N],leave=0;
inline void pushup(int p){siz[p]=siz[son[p][0]]+siz[son[p][1]]+1;}
inline int newnode(int v){rd[++cnt]=rand(),val[cnt]=v,son[cnt][0]=son[cnt][1]=0,siz[cnt]=1;return cnt;}
inline int merge(int a,int b){
if(!a||!b)return a+b;
if(rd[a]<=rd[b]){son[a][1]=merge(son[a][1],b),pushup(a);return a;}
son[b][0]=merge(a,son[b][0]),pushup(b);return b;
}
inline res split(int p,int k){
if(!p)return make_pair(0,0);
res ans,tmp;
if(siz[son[p][0]]>=k){
tmp=split(son[p][0],k);
ans.first=tmp.first,son[p][0]=tmp.second,pushup(p),ans.second=p;
return ans;
}
tmp=split(son[p][1],k-siz[son[p][0]]-1);
ans.second=tmp.second,son[p][1]=tmp.first,pushup(p),ans.first=p;
return ans;
}
inline int rank(int p,int v){
if(!p)return 0;
if(val[p]>=v)return rank(son[p][0],v);
return siz[son[p][0]]+1+rank(son[p][1],v);
}
inline void ins(int v){
int k=rank(rt,v),p=newnode(v);
res x=split(rt,k);
rt=merge(merge(x.first,p),x.second);
}
inline void del(){
int k=rank(rt,minn-delta);
res x=split(rt,k);
rt=x.second,leave+=siz[x.first];
}
inline int kth(int p,int k){
int rk=son[p][0]?siz[son[p][0]]+1:1;
if(k==rk)return val[p];
if(k<rk)return kth(son[p][0],k);
return kth(son[p][1],k-siz[son[p][0]]-1);
}
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int main(){
srand(time(NULL));
n=read(),minn=read();
while(n--){
char op[2];
int k;
scanf("%s%d",op,&k);
if(op[0]=='I'&&k>=minn)ins(k-delta);
if(op[0]=='A')delta+=k;
if(op[0]=='S')delta-=k,del();
if(op[0]=='F')printf("%d\n",k>siz[rt]?-1:kth(rt,siz[rt]-k+1)+delta);
}
printf("%d",leave);
return 0;
}