BZOJ 題目1503: [NOI2004]郁悶的出納員（SBT+延遲操作）

Description

OIER公司是一家大型專業化軟件公司，有著數以萬計的員工。作為一名出納員，我的任務之一便是統計每位員工的工資。這本來是一份不錯的工作，但是令人郁悶的是，我們的老板反復無常，經常調整員工的工資。如果他心情好，就可能把每位員工的工資加上一個相同的量。反之，如果心情不好，就可能把他們的工資扣除一個相同的量。我真不知道除了調工資他還做什麼其它事情。工資的頻繁調整很讓員工反感，尤其是集體扣除工資的時候，一旦某位員工發現自己的工資已經低於了合同規定的工資下界，他就會立刻氣憤地離開公司，並且再也不會回來了。每位員工的工資下界都是統一規定的。每當一個人離開公司，我就要從電腦中把他的工資檔案刪去，同樣，每當公司招聘了一位新員工，我就得為他新建一個工資檔案。老板經常到我這邊來詢問工資情況，他並不問具體某位員工的工資情況，而是問現在工資第k多的員工拿多少工資。每當這時，我就不得不對數萬個員工進行一次漫長的排序，然後告訴他答案。好了，現在你已經對我的工作了解不少了。正如你猜的那樣，我想請你編一個工資統計程序。怎麼樣，不是很困難吧？

Input

Output

輸出文件的行數為F命令的條數加一。對於每條F命令，你的程序要輸出一行，僅包含一個整數，為當前工資第k多的員工所拿的工資數，如果k大於目前員工的數目，則輸出-1。輸出文件的最後一行包含一個整數，為離開公司的員工的總數。

Sample Input

Sample Output

HINT

I命令的條數不超過100000 A命令和S命令的總條數不超過100 F命令的條數不超過100000 每次工資調整的調整量不超過1000 新員工的工資不超過100000

Source

Splay

還是很簡單的，就是多了一點技巧，就是延遲操作，因為每回每個都要加或減，沒有必要加減都個更新一回樹，存一個整形變量最後加就行了，就是減的時候有可能工資低於最低標准了之後會離開公司，所以要更新一下，如果這個點的key值小於min，那麼他的左子樹都小於min，所以root直接等於右子樹，從右子樹找，否則大的話，右子樹都大，找他左子樹，最後更新一下size。

我也是醉了，，最後輸出離開公司的人數，，題目不是說讀入的時候下小於min直接離開公司嗎，，那不也叫離開公司嗎，，那部分人居然不算。。

ac代碼

/**************************************************************
    Problem: 1503
    User: kxh1995
    Language: C++
    Result: Accepted
    Time:640 ms
    Memory:16444 kb
****************************************************************/
 
#include
#include
struct s  
{  
    int key,left,right,size;  
}tree[1001000];  
int top,root;  
void left_rot(int &x)    
{    
    int y=tree[x].right;    
    tree[x].right=tree[y].left;    
    tree[y].left=x;    
    tree[y].size=tree[x].size;    
    tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;    
    x=y;    
}   
void right_rot(int &x)     
{    
    int y=tree[x].left;    
    tree[x].left=tree[y].right;    
    tree[y].right=x;    
    tree[y].size=tree[x].size;    
    tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;    
    x=y;    
}  
void maintain(int &x,bool flag)//維護SBT狀態      
{    
    if(flag==false)   
    {    
        if(tree[tree[tree[x].left].left].size>tree[tree[x].right].size)    
            right_rot(x);    
        else   
            if(tree[tree[tree[x].left].right].size>tree[tree[x].right].size)     
            {    
                left_rot(tree[x].left);    
                right_rot(x);       
            }    
            else   
                return;    
    }    
    else 
    {    
        if(tree[tree[tree[x].right].right].size>tree[tree[x].left].size)    
            left_rot(x);    
        else   
            if(tree[tree[tree[x].right].left].size>tree[tree[x].left].size)     
            {    
                right_rot(tree[x].right);    
                left_rot(x);    
            }    
            else   
                return;    
    }    
    maintain(tree[x].left,false);    
    maintain(tree[x].right,true);    
    maintain(x,true);    
    maintain(x,false);    
}    
void insert(int &x,int key)  
{  
    if(x==0)  
    {  
        x=++top;  
        tree[x].left=0;  
        tree[x].right=0;  
        tree[x].size=1;  
        tree[x].key=key;  
    }  
    else 
    {  
        tree[x].size++;  
        if(key=tree[x].key);  
    }  
}  
int remove(int &x,int key)   
{  
    tree[x].size--;  
    if(key>tree[x].key)  
        remove(tree[x].right,key);  
    else 
        if(key