这道题用treap写其实更适合，但是因为要熟悉splay的写法就写一遍splay啦。
然后没什么难的，就当是模版了吧！
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> const int M=1e5+10; using namespace std; int n,mni,kk,root=0,now,sz=0,aa=0,tt,num=0,q=0; int a[M],t[M][2],f[M],s[M]; int read() { int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();} return ans*f; } void count(int x){s[x]=s[t[x][0]]+s[t[x][1]]+1;} void insert(int fa,int &y,int x) { if(!y){y=++sz;now=y;a[y]=x;f[y]=fa;} else if(x<a[y])insert(y,t[y][0],x); else insert(y,t[y][1],x); count(y); } void rotate(int x,int &p) { if(p==f[x])p=x; int k=x==t[f[x]][1]; int y=f[x]; t[y][k]=t[x][!k];f[t[x][!k]]=y;t[x][!k]=y; if(f[y])t[f[y]][y==t[f[y]][1]]=x;f[x]=f[y];f[y]=x;s[x]=s[y]; count(y); } void splay(int x,int &r) { for(int fa=f[r];f[x]!=fa;) { if(f[f[x]]==fa){rotate(x,r);break;} int X=x==t[f[x]][1],Y=f[x]==t[f[f[x]]][1]; if(X^Y)rotate(x,r),rotate(x,r); else rotate(f[x],r),rotate(x,r); } } void del(int y,int x) { if(!y)return; if(a[y]<x){tt=y;del(t[y][1],x);} else del(t[y][0],x); } int find(int x,int ra) { while(1) { if(ra<=s[t[x][0]]){x=t[x][0];continue;} if(ra==s[t[x][0]]+1)break; ra-=s[t[x][0]]+1;x=t[x][1]; } return x; } int main() { n=read();mni=read(); aa=0; char str[3]; for(int i=1;i<=n;i++) { scanf("%s %d",str,&kk); if(str[0]=='I'&&kk>=mni)q++,insert(0,root,kk-aa),splay(now,root); else if(str[0]=='A')aa+=kk; else if(str[0]=='S'){ aa-=kk;tt=0;del(root,mni-aa);if(!tt)continue; splay(tt,root);int x=t[tt][0];num+=s[x]+1;root=t[tt][1];f[root]=0; } else if(str[0]=='F') { if(kk>s[root])printf("-1 "); else tt=find(root,s[root]-kk+1),printf("%d ",a[tt]+aa); } } printf("%d",num); return 0; }