平衡树简单题。

直接用fhgtreap实现分裂和合并就没了。

代码：

#include
    
     #define N 100005using namespace std;typedef pair
     
       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
      
       =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;}