1 #include <cstdio> 2 using namespace std; 3 int son[110001][2],father[110001],size[110001],val[110001],cnt[110001],n,i,now,min,x,y,rt,top,ans,m; 4 char ch[100]; 5 void newnode(int &x,int fa,int data){ 6     x=++top; 7     father[x]=fa; 8     val[x]=data; 9     size[top]=1;10     son[x][0]=son[x][1]=0;11 }12 void rot(int x,int k){13     int y=father[x];14     son[y][!k]=son[x][k];15     father[son[x][k]]=y;16     father[x]=father[y];17     son[father[y]][son[father[y]][1]==y]=x;18     son[x][k]=y;19     father[y]=x;20     size[x]=size[y];21     size[y]=size[son[y][0]]+size[son[y][1]]+1;22 }23 void rots(int x,int g){24     while((y=father[x])!=g){25         if(father[father[x]]==g) rot(x,son[father[x]][0] == x);26         else27         {28             int y=father[x],z=father[y],f=(son[z][0]==y);29             if(son[y][f]==x)rot(x,!f);else rot(y,f);30             rot(x,f);31         }32     }33     if(!g) rt=x;34 }35 void ins(int a){36     int x=rt;37     if (!rt){38         rt=++top;val[rt]=a;39         son[rt][0]=son[rt][1]=0;40         size[rt]=1;41     }42     else{43     while(son[x][val[x]<a]) {size[x]++;x=son[x][val[x]<a];}44     size[x]++;45     newnode(son[x][val[x]<a],x,a);46     rots(son[x][val[x]<a],0);47     }48 }49 void del(int a,int x,int fa){50     if (!x)return;51     if (val[x]<a){52         if (x==rt) rt=son[x][1];53         father[son[x][1]]=fa;54         son[fa][x==son[fa][1]]=son[x][1];55         del(a,son[x][1],fa);56         now+=size[son[x][0]]+1;ans+=size[son[x][0]]+1;57     }else {del(a,son[x][0],x);}58     size[x]=size[x]-now;59 }60 int find(int k,int x){61     if(k<=size[son[x][0]])return find(k,son[x][0]);62     if(k==size[son[x][0]]+1)return val[x]-min+m;63     return find(k-size[son[x][0]]-1,son[x][1]);64 }65 int main(){66     scanf("%d%d",&n,&m);67     for (i=1;i<=n;i++){68         scanf("%s%d",&ch,&x);69         if (ch[0]==‘I‘)if (x>=m)ins(x-m+min);70         if (ch[0]==‘A‘)min-=x;71         if (ch[0]==‘S‘){min+=x;now=0;del(min,rt,0);}72         if (ch[0]==‘F‘)if (x>size[rt]) printf("-1\n");else printf("%d\n",find(size[rt]-x+1,rt));73     }74     printf("%d\n",ans);75 }