OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？
输出文件的行数为F命令的条数加一。对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。输出文件的最后一行包含一个整数，为离开公司的员工的总数。
I命令的条数不超过100000 A命令和S命令的总条数不超过100 F命令的条数不超过100000 每次工资调整的调整量不超过1000 新员工的工资不超过100000
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<ctime> 5 using namespace std; 6 struct data{ 7 int l,r,num,rnd,s; 8 }tr[100001]; 9 int n,m; 10 int root,cnt,ans,delta; 11 void updata(int k){tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;} 12 void rturn(int &k){ 13 int t=tr[k].l; 14 tr[k].l=tr[t].r; 15 tr[t].r=k; 16 tr[t].s=tr[k].s; 17 updata(k); 18 k=t; 19 } 20 21 void lturn(int &k){ 22 int t=tr[k].r; 23 tr[k].r=tr[t].l; 24 tr[t].l=k; 25 tr[t].s=tr[k].s; 26 updata(k); 27 k=t; 28 } 29 30 void insert(int &k,int x){ 31 32 if (k==0){ 33 cnt++; k=cnt; tr[k].rnd=rand(); tr[k].num=x; tr[k].s=1; return; 34 } 35 tr[k].s++; 36 if (x<tr[k].num){ 37 insert(tr[k].l,x); 38 if (tr[tr[k].l].rnd<tr[k].rnd) rturn(k); 39 } 40 else{ 41 insert(tr[k].r,x); 42 if (tr[tr[k].r].rnd<tr[k].rnd) lturn(k); 43 } 44 } 45 46 int del(int &k,int x){//这里刚开始偷懒，后来就一直wa 47 int t,l=tr[k].l,r=tr[k].r; 48 if (k==0) return 0; 49 if (tr[k].num<x) { 50 k=tr[k].r; 51 return tr[l].s+del(k,x)+1;} 52 else { 53 t=del(tr[k].l,x);tr[k].s-=t;return t; 54 } 55 } 56 57 int find(int k,int x){ 58 int l=tr[k].l,r=tr[k].r; 59 if (tr[l].s+1==x) return tr[k].num+delta; 60 else if (tr[l].s+1<x) return find(r,x-tr[l].s-1); 61 else return find(l,x); 62 } 63 64 int main(){ 65 scanf("%d%d",&n,&m); 66 char ch[1];int x; 67 while (n--){ 68 scanf("%s%d",ch,&x); 69 if (ch[0]==‘I‘) if (x>=m) insert(root,x-delta); 70 if (ch[0]==‘S‘) { 71 delta-=x; ans+=del(root,m-delta); 72 } 73 if (ch[0]==‘A‘) delta+=x; 74 if (ch[0]==‘F‘) { 75 //if (x>tr[root].s) printf("-1\n"); 76 if(x>tr[root].s)printf("-1\n"); 77 else printf("%d\n",find(root,tr[root].s-x+1)); 78 } 79 } 80 printf("%d",ans); 81 }
splay（错的）
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=100010; 6 int tr[maxn][2],fa[maxn],num[maxn],ans,n,x,t1,t2,size1=0,rt, 7 size[maxn],delta,Min; 8 9 void pushup(int x){ 10 size[x]=size[tr[x][1]]+size[tr[x][0]]+1; 11 } 12 13 void rotate(int x,int &k){ 14 int y,z,l,r; 15 y=fa[x],z=fa[y]; 16 if (tr[y][0]==x)l=0;else l=1; r=l^1; 17 if (y==k) k=x; 18 else {if (tr[z][0]==y)tr[z][0]=x; else tr[z][1]=x;} 19 fa[x]=z; fa[y]=x; fa[tr[x][r]]=y; 20 tr[y][l]=tr[x][r]; tr[x][r]=y; 21 pushup(x);pushup(y); 22 } 23 24 void splay(int x,int &k){ 25 int y,z; 26 while (x!=k){ 27 y=fa[x],z=fa[y]; 28 if (y!=k){ 29 if ((tr[z][0]==y)^(tr[y][0]==x)) rotate(x,rt); 30 else rotate(y,rt); 31 } 32 rotate(x,rt); 33 } 34 } 35 36 void insert(int x,int &k,int last){ 37 if (!k){ 38 size1++;k=size1;num[k]=x;fa[k]=last;size[k]=1;splay(k,rt);return; 39 } 40 if (x>=num[k]) insert(x,tr[k][1],k); else insert(x,tr[k][0],k); 41 // pushup(k); 42 } 43 44 45 int find(int &k,int rank){ 46 int l=tr[k][0],r=tr[k][1]; 47 if (size[r]+1==rank) return k; 48 else if (size[r]>=rank) return find(r,rank); 49 else return find(l,rank-size[r]-1); 50 } 51 52 int dec(int &x,int f){ 53 if (!x) return 0; 54 int mid; 55 if (num[x]+delta<Min){ 56 mid=dec(tr[x][1],x)+size[tr[x][0]]+1; 57 size[tr[x][1]]=size[x]-mid; 58 x=tr[x][1];fa[x]=f; 59 } 60 else{ 61 mid=dec(tr[x][0],x); 62 size[x]-=mid; 63 } 64 return mid; 65 } 66 67 int main(){ 68 char ch[1]; 69 int x,j; 70 scanf("%d%d",&n,&Min); 71 while(n--){ 72 scanf("%s%d",&ch,&x); 73 if (ch[0]==‘I‘){if (x-delta<Min) ; else insert(x-delta,rt,0);} 74 if (ch[0]==‘A‘) delta+=x; 75 if (ch[0]==‘S‘) { 76 delta-=x; int mid=dec(rt,0); 77 ans+=mid; 78 } 79 if (ch[0]==‘F‘) { 80 if (x>size[rt]) printf("-1\n"); 81 else printf("%d\n",num[find(rt,x)]+delta); 82 } 83 } 84 printf("%d\n",ans); 85 }
原文：http://www.cnblogs.com/wuminyan/p/5125763.html