题目大意：
给4种操作
I：添加一个员工工资信息
A：增加所有员工的工资
S：减少所有员工的工资
F：询问工资第k高的员工的工资情况
自己做的第一道splay树的题目，初学找找感觉
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using namespace std; 6 int n,m,w,limit; 7 const int N = 100010; 8 #define ls ch[x][0] 9 #define rs ch[x][1] 10 struct SplayTree{ 11 //sum[i]记录i以及其子树中的点的总个数,cnt[i]记录与i号位置取值相等的点的个数 12 int val[N] , cnt[N] , sum[N]; 13 int all; //统计离开公司的员工的总人数，也就是相当于计算删除的点的个数 14 int ch[N][2]; 15 int pre[N]; 16 int rt , top; 17 18 void init() 19 { 20 ch[0][0] = ch[0][1] = pre[0] = sum[0] = cnt[0] = 0; 21 all = rt = top = 0; 22 } 23 24 void newNode(int &x , int c) 25 { 26 x = ++top; 27 ch[x][0] = ch[x][1] = pre[x] = 0; 28 cnt[x] = sum[x] = 1 , val[x]=c; 29 } 30 //通过左右子节点更新父节点 31 void up(int x){ 32 sum[x] = sum[ch[x][0]]+sum[ch[x][1]]+cnt[x]; 33 } 34 35 void Rotate(int x , int f) //f==1表示右旋，也就是x属于父亲的左子树上 36 { 37 int y=pre[x]; 38 ch[y][!f] = ch[x][f]; 39 pre[ch[x][f]]=y; 40 if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; 41 pre[x]=pre[y]; 42 pre[y]=x; 43 ch[x][f]=y; 44 up(y); 45 } 46 47 void Splay(int x , int goal) 48 { 49 while(pre[x] != goal){ 50 if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][0] == x); 51 else{ 52 int y=pre[x] , z=pre[y]; 53 int f=(ch[z][0] == y); 54 if(ch[y][f] == x) Rotate(x , !f) , Rotate(x , f); 55 else Rotate(y,f) , Rotate(x,f); 56 } 57 } 58 up(x); 59 if(goal == 0) rt = x; 60 } 61 62 void insert(int &x , int key , int fa) 63 { 64 //一直向下找到空的叶子节点插入当前的值 65 if(!x){ 66 newNode(x , key); 67 pre[x]=fa; 68 Splay(x , 0); 69 return; 70 } 71 if(key == val[x]){ 72 cnt[x]++; 73 sum[x]++; 74 Splay(x,0); 75 return ; 76 } 77 //点插入左子树 78 else if(key<val[x]){ 79 insert(ch[x][0] , key , x); 80 } 81 //点插入右子树 82 else { 83 insert(ch[x][1] , key , x); 84 } 85 up(x); 86 } 87 88 void del(int &x , int fa) 89 { 90 //一直访问到空的叶子节点结束 91 if(!x) return ; 92 //当前点的工资满足要求，那么只要考虑其左子树上要删除多少点 93 if(val[x] >= limit) del(ch[x][0] , x); 94 else{ 95 /*当前点的工资不满足要求，那么这个点和其左子树都是不满足要求的 96 ,all记录当前点和左子树删除的点的总数*/ 97 all+=sum[ch[x][0]]+cnt[x]; 98 x=ch[x][1]; 99 //当前点被删除，连接关系要进行修改 100 pre[x]=fa; 101 if(fa == 0) rt = x; 102 del(x,fa); 103 } 104 if(x) up(x); 105 } 106 107 void update() 108 { 109 del(rt , 0); 110 } 111 112 int find_kth(int x , int k) 113 { 114 if(k<sum[ch[x][0]]+1) return find_kth(ch[x][0] , k); 115 else if(k > sum[ch[x][0]]+cnt[x]) 116 return find_kth(ch[x][1] , k-sum[ch[x][0]]-cnt[x]); 117 else{ 118 Splay(x , 0); 119 return x; 120 } 121 } 122 }spt; 123 124 int main() 125 { 126 // freopen("a.in" , "r" , stdin); 127 char op[10]; 128 int t; 129 while(~scanf("%d%d" , &n , &m)) 130 { 131 spt.init(); 132 for(int i=0 ; i<n ; i++){ 133 scanf("%s%d" , op , &t); 134 if(op[0] == 'I'){ 135 if(t<m) 136 continue; 137 spt.insert(spt.rt , t-w , 0); 138 } 139 else if(op[0] == 'A') w+=t; 140 else if(op[0] == 'S'){ 141 w-=t; 142 limit=m-w; 143 spt.update(); 144 } 145 else{ 146 int sum = spt.sum[spt.rt]; 147 if(t>sum) printf("-1 "); 148 else{ 149 printf("%d " , spt.val[spt.find_kth(spt.rt , sum-t+1)]+w); 150 } 151 } 152 // cout<<"sum: "<<spt.sum[spt.rt]<<endl; 153 } 154 printf("%d " , spt.all); 155 } 156 return 0; 157 }