试图写splay，然而最终还是不得不向题解屈服了。
虽然差不多领会了精神，但是实际写代码还是很艰难。
继续刷熟练度……
代码学自hzwer：
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=100010; 10 int n,m; 11 int tot=0; 12 int change=0; 13 // 14 struct node{ 15 int fa,l,r; 16 int v,num; 17 int size; 18 }tr[mxn]; 19 int root,cnt; 20 void fsize(int rt){tr[rt].size=tr[tr[rt].l].size+tr[tr[rt].r].size+1;return;} 21 void zig(int &x){ 22 int y=tr[x].fa; 23 int z=tr[y].fa; 24 if(y==tr[z].l) tr[z].l=x; 25 else tr[z].r=x; 26 tr[x].fa=z; 27 tr[y].l=tr[x].r; 28 tr[tr[x].r].fa=y; 29 tr[x].r=y; 30 tr[y].fa=x; 31 fsize(y);fsize(x); 32 if(y==root)root=x; 33 } 34 void zag(int &x){ 35 int y=tr[x].fa; 36 int z=tr[y].fa; 37 if(y==tr[z].l) tr[z].l=x; 38 else tr[z].r=x; 39 tr[x].fa=z; 40 tr[y].r=tr[x].l; 41 tr[tr[x].l].fa=y; 42 tr[y].fa=x; 43 tr[x].l=y; 44 fsize(y);fsize(x); 45 if(y==root)root=x; 46 } 47 void splay(int &x,int d){ 48 while(tr[x].fa!=d){ 49 if(tr[tr[x].fa].l==x)zig(x); 50 else zag(x); 51 } 52 } 53 void insert(int k){ 54 if(!root){ 55 root=++cnt; 56 tr[cnt].num=k; 57 tr[cnt].size=1; 58 return; 59 } 60 int p=root; 61 int z; 62 while(p){ 63 z=p; 64 ++tr[p].size; 65 if(k<tr[p].num)p=tr[p].l; 66 else p=tr[p].r; 67 } 68 if(tr[z].num>k) tr[z].l=++cnt; 69 else tr[z].r=++cnt; 70 tr[cnt].num=k;tr[cnt].size=1;tr[cnt].fa=z; 71 splay(cnt,0); 72 } 73 int find(int x,int k){ 74 if(k<=tr[tr[x].r].size)return find(tr[x].r,k); 75 if(k==tr[tr[x].r].size+1)return tr[x].num; 76 return find(tr[x].l,k-tr[tr[x].r].size-1); 77 } 78 int del(int &x,int f){ 79 if(!x)return 0; 80 int k; 81 if(tr[x].num+change<m){ 82 k=del(tr[x].r,x)+tr[tr[x].l].size+1;//统计删除个数 83 tr[tr[x].r].size=tr[x].size-k; 84 x=tr[x].r;tr[x].fa=f;//用右儿子替代当前结点 85 } 86 else{ 87 k=del(tr[x].l,x); 88 tr[x].size-=k; 89 } 90 return k; 91 } 92 93 int main(){ 94 scanf("%d%d",&n,&m); 95 int i,j; 96 char op[3];int x; 97 while(n--){ 98 scanf("%s%d",op,&x); 99 switch(op[0]){ 100 case 'I':{ 101 if(x>=m)insert(x-change); 102 break; 103 } 104 case 'A':{ 105 change+=x; 106 break; 107 } 108 case 'S':{ 109 change-=x; 110 tot+=del(root,0); 111 break; 112 } 113 case 'F':{ 114 if(x>tr[root].size){printf("-1 ");} 115 else printf("%d ",find(root,x)+change); 116 break; 117 } 118 } 119 } 120 printf("%d ",tot); 121 122 return 0; 123 }