本文共 6325 字，大约阅读时间需要 21 分钟。

题目大意就不说了，很多地方都能见到原题，平衡树必刷题之一。

Input：

第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。

接下来的n行，每行表示一条命令。命令可以是以下四种之一：

_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。

在初始时，可以认为公司里一个员工也没有。、

Output：

输出文件的行数为F命令的条数加一。

对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。

输出文件的最后一行包含一个整数，为离开公司的员工的总数。

思路：显然的平衡树解决的问题，我分别用Treap和Splay写了，速度上Treap快（常数小），Splay就当是练手了。

注意一点在树结构外维护的数据。因为题目要求总共离开的人数，所以一定要记录离开的人数。

在改钱数的时候当然不能去树里面一个一个改，那样时间复杂度就退化了。我的做法是维护一个改变的钱数，然后在加入和取出的时候加加减减满足题意就可以了。详见代码。

CODE(Splay)

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define INF 0x7f7f7f7fusing 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);}
      
     
    
   

#include 
   
    #include 
    
     #include 
     
      #include 
      
       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<
       
        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;}
       
      
     
    
   

转载地址：https://blog.csdn.net/jiangyuze831/article/details/39025911 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！