题目大意就不说了，很多地方都能见到原题，平衡树必刷题之一。
Input：
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。
接下来的n行，每行表示一条命令。命令可以是以下四种之一：
|
名称 |
格式 |
作用 |
|
I命令 |
I_k |
新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。 |
|
A命令 |
A_k |
把每位员工的工资加上k |
|
S命令 |
S_k |
把每位员工的工资扣除k |
|
F命令 |
F_k |
查询第k多的工资 |
_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。
在初始时，可以认为公司里一个员工也没有。、
Output：
输出文件的行数为F命令的条数加一。
对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。
思路：显然的平衡树解决的问题，我分别用Treap和Splay写了，速度上Treap快（常数小），Splay就当是练手了。
注意一点在树结构外维护的数据。因为题目要求总共离开的人数，所以一定要记录离开的人数。
在改钱数的时候当然不能去树里面一个一个改，那样时间复杂度就退化了。我的做法是维护一个改变的钱数，然后在加入和取出的时候加加减减满足题意就可以了。详见代码。
CODE(Splay)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x7f7f7f7f
using namespace std;
struct Complex{
int val,cnt,size;
Complex *son[2],*father;
void Maintain();
int Compare(int x) {
if(x == val) return -1;
return x > val;
}
bool Check() {
return father->son[1] == this;
}
}none,*nil = &none,*root = nil;
int cnt,low;
int added,total_away;
char s[10];
inline Complex *NewNode(Complex *f,int x);
inline void Rotate(Complex *a,bool dir);
inline void Splay(Complex *a,Complex *aim);
inline void Insert(int x);
int FindSucc(Complex *a,int x);
Complex *Find(Complex *a,int x);
int FindK(Complex *a,int k);
int main()
{
nil->son[0] = nil->son[1] = nil;
cin >> cnt >> low;
for(int x,i = 1;i <= cnt; ++i) {
scanf("%s%d",s,&x);
switch(s[0]) {
case 'I': {
if(x >= low) Insert(x - added);
break;
}
case 'A':added += x;break;
case 'S': {
added -= x;
int limit = low - added;
int succ = FindSucc(root,limit);
if(succ != INF) {
Splay(Find(root,succ),nil);
total_away += root->son[0]->size;
root->size -= root->son[0]->size;
root->son[0] = nil;
}
else {
total_away += root->size;
root = nil;
}
break;
}
case 'F': {
if(x > root->size) puts("-1");
else printf("%d\n",FindK(root,root->size - x + 1) + added);
break;
}
}
}
cout << total_away;
return 0;
}
void Complex :: Maintain()
{
if(this == nil) return ;
size = cnt + son[0]->size + son[1]->size;
}
inline Complex *NewNode(Complex *f,int x)
{
Complex *re = new Complex();
re->val = x;
re->son[0] = re->son[1] = nil;
re->father = f;
re->cnt = re->size = 1;
return re;
}
inline void Rotate(Complex *a,bool dir)
{
Complex *f = a->father;
f->son[!dir] = a->son[dir];
f->son[!dir]->father = f;
a->son[dir] = f;
a->father = f->father;
f->father->son[f->Check()] = a;
f->father = a;
f->Maintain(),a->Maintain();
if(root == f) root = a;
}
inline void Splay(Complex *a,Complex *aim)
{
while(a->father != aim) {
if(a->father->father == aim)
Rotate(a,!a->Check());
else if(!a->father->Check()) {
if(!a->Check()) {
Rotate(a->father,true);
Rotate(a,true);
}
else {
Rotate(a,false);
Rotate(a,true);
}
}
else {
if(a->Check()) {
Rotate(a->father,false);
Rotate(a,false);
}
else {
Rotate(a,true);
Rotate(a,false);
}
}
a->Maintain();
}
}
inline void Insert(int x)
{
if(root == nil) {
root = NewNode(nil,x);
return ;
}
Complex *now = root;
while(true) {
now->size++;
int dir = now->Compare(x);
if(dir == -1) {
now->cnt++;
return ;
}
if(now->son[dir] == nil) {
now->son[dir] = NewNode(now,x);
Splay(now->son[dir],nil);
return ;
}
now = now->son[dir];
}
}
int FindSucc(Complex *a,int x)
{
if(a == nil) return INF;
if(a->val < x) return FindSucc(a->son[1],x);
return min(a->val,FindSucc(a->son[0],x));
}
Complex *Find(Complex *a,int x)
{
int dir = a->Compare(x);
if(dir == -1) return a;
return Find(a->son[dir],x);
}
int FindK(Complex *a,int k)
{
if(k <= a->son[0]->size)
return FindK(a->son[0],k);
k -= a->son[0]->size;
if(k <= a->cnt)
return a->val;
k -= a->cnt;
return FindK(a->son[1],k);
}
CODE(Traep很久以前的代码了。。自己都看不懂了。。)：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct Complex{
int val,random,cnt,size;
Complex* son[2];
Complex(){
cnt=size=1;
random=rand();
son[0]=son[1]=NULL;
}
inline int Compare(int x){
if(x==val) return -1;
return x>val;
}
inline void Maintain(){
size=cnt;
if(son[0]!=NULL) size+=son[0]->size;
if(son[1]!=NULL) size+=son[1]->size;
}
}*root;
int asks,min_money;
int g_add,ans;
inline void Rotate(Complex*& a,int dir);
void Insert(Complex*& a,int x);
void Delete(Complex*& a,int x);
int FindK(Complex* a,int k);
inline int FindMin();
int main()
{
cin>>asks>>min_money;
for(int x,i=1;i<=asks;i++){
char c[10];
scanf("%s%d",c,&x);
if(c[0]=='I'){
if(x>=min_money)
Insert(root,x-g_add);
}
else if(c[0]=='A') g_add+=x;
else if(c[0]=='S'){
g_add-=x;
while(1){
int x=FindMin();
if(x==-0x7f7f7f7f||x+g_add>=min_money) break;
Delete(root,x);
ans++;
}
}
else{
if(root==NULL||x>root->size) printf("-1\n");
else printf("%d\n",FindK(root,root->size-x+1)+g_add);
}
}
cout<<ans;
return 0;
}
inline void Rotate(Complex*& a,int dir)
{
Complex* k=a->son[dir^1];
a->son[dir^1]=k->son[dir];
k->son[dir]=a;
a->Maintain(),k->Maintain();
a=k;
}
void Insert(Complex*& a,int x)
{
if(a==NULL){
a=new Complex();
a->val=x;
return ;
}
int dir=a->Compare(x);
if(dir==-1)
a->cnt++;
else{
Insert(a->son[dir],x);
if(a->son[dir]->random > a->random)
Rotate(a,dir^1);
}
a->Maintain();
}
void Delete(Complex*& a,int x)
{
int dir=a->Compare(x);
if(dir!=-1)
Delete(a->son[dir],x);
else{
if(a->cnt>1)
a->cnt--;
else{
if(a->son[0]==NULL) a=a->son[1];
else if(a->son[1]==NULL) a=a->son[0];
else{
int _dir=(a->son[0]->random > a->son[1]->random)?1:0;
Rotate(a,_dir);
Delete(a->son[_dir],x);
}
}
}
if(a!=NULL) a->Maintain();
}
int FindK(Complex* a,int k)
{
int t=0;
if(a->son[0]!=NULL)
t=a->son[0]->size;
if(k<=t)
return FindK(a->son[0],k);
if(k>t+a->cnt)
return FindK(a->son[1],k-t-a->cnt);
return a->val;
}
inline int FindMin()
{
if(root==NULL) return -0x7f7f7f7f;
Complex* now=root;
while(now->son[0]!=NULL)
now=now->son[0];
return now->val;
}