BZOJ 1503 郁悶的出納員 二叉平衡樹（Treap，Splay）

題目大意就不說了，很多地方都能見到原題，平衡樹必刷題之一。

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