【前言】快要省選二試了。上次去被虐出翔了~~這次即便是打醬油，也要打出風采！於是暫停新東西的學習，然後開始復習以前的知識，為騙分做准備。PS：區間翻轉的暫時跳過，就算學了也來不及鞏固了。
【BZOJ3224】
3224: Tyvj 1728 普通平衡樹
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1477 Solved: 570
Description
您需要寫一種數據結構（可參考題目標題），來維護一些數，其中需要提供以下操作：
1. 插入x數
2. 刪除x數(若有多個相同的數，因只刪除一個)
3. 查詢x數的排名(若有多個相同的數，因輸出最小的排名)
4. 查詢排名為x的數
5. 求x的前驅(前驅定義為小於x，且最大的數)
6. 求x的後繼(後繼定義為大於x，且最小的數)
Input
第一行為n，表示操作的個數,下面n行每行有兩個數opt和x，opt表示操作的序號(1<=opt<=6)
Output
對於操作3,4,5,6每行輸出一個數，表示對應答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
【分析】寫了半個下午，調了一個晚上，這是多麼的壯烈啊。
splay的基本操作。因為剛開始復習，這一段的rotate和splay直接copy模板的咕~~(╯﹏╰)b。
對於相同的數，處理起來很麻煩。YD表示可以用一個count[x]記錄x出現的次數。而我是傻的，直接插入進去。這樣的話，我還記錄了num[i][w]，表示以i節點的左右子樹的大小。（只需在rotate的時候改變一下即可）
查詢K的排名時，只需把K再插入一遍（<=的形式插），再旋轉至根，答案就是num[k][1]+1。
還有，有關前驅和後繼真是煩人（萬一有重復！）。對此，YY教了我一個亂使的方法。每次對於K求出它的前驅（後繼）P，如果P
【代碼】
/**************************************************************
Problem: 3224
User: jiangshibiao
Language: C++
Result: Accepted
Time:696 ms
Memory:7080 kb
****************************************************************/
#include
#define N 200005
using namespace std;
int son[N][3],num[N][3],f[N],a[N];
int opt,n,i,root,x,node,ans,flag;
inline void Rotate(int x,int w)//1:左旋；2：右旋
{
int y=f[x],z=f[y];
son[y][3-w]=son[x][w];
if (son[x][w]) f[son[x][w]]=y;
f[x]=z;
num[y][3-w]=num[x][w];
num[x][w]+=num[y][w]+1;
if (z)
{
if (y==son[z][1]) son[z][1]=x;
else son[z][2]=x;
}
f[y]=x;son[x][w]=y;
}
inline void splay(int x)
{
int y;
while (f[x])
{
y=f[x];
if (!f[y])
{
if (x==son[y][1]) Rotate(x,2);else Rotate(x,1);
continue;
}
if (y==son[f[y]][1])
{
if (x==son[y][1]) Rotate(y,2),Rotate(x,2);
else Rotate(x,1),Rotate(x,2);
}
else
{
if (x==son[y][2]) Rotate(y,1),Rotate(x,1);
else Rotate(x,2),Rotate(x,1);
}
}
root=x;
}
inline void insert(int x,int add)
{
if (add<=a[x])
{
if (!son[x][1]) son[x][1]=++node,a[node]=add,f[node]=x;
else insert(son[x][1],add);
num[x][1]++;
}
else
{
if (!son[x][2]) son[x][2]=++node,a[node]=add,f[node]=x;
else insert(son[x][2],add);
num[x][2]++;
}
}
inline void del(int x,int add)
{
if (!x) return;
if (add==a[x])
{
splay(x);
if (!son[x][1]&&!son[x][2]){root=0;return;}
if (!son[x][1]) {root=son[x][2];f[son[x][2]]=0;return;}
if (!son[x][2]) {root=son[x][1];f[son[x][1]]=0;return;}
int find=son[x][1],temp=son[x][2];
while (son[find][2]) find=son[find][2];
splay(find);son[find][2]=temp;f[temp]=find;
return;
}
if (add
【BZOJ1056/1862】
1862: [Zjoi2006]GameZ游戲排名系統
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 554 Solved: 212
Description
GameZ為他們最新推出的游戲開通了一個網站。世界各地的玩家都可以將自己的游戲得分上傳到網站上。這樣就可以看到自己在世界上的排名。得分越高，排名就越靠前。當兩個玩家的名次相同時，先上傳記錄者優先。由於新游戲的火爆，網站服務器已經難堪重負。為此GameZ雇用了你來幫他們重新開發一套新的核心。排名系統通常要應付三種請求：上傳一條新的得分記錄、查詢某個玩家的當前排名以及返回某個區段內的排名記錄。當某個玩家上傳自己最新的得分記錄時，他原有的得分記錄會被刪除。為了減輕服務器負擔，在返回某個區段內的排名記錄時，最多返回10條記錄。
Input
第一行是一個整數n（n>=10）表示請求總數目。接下來n行每行包含了一個請求。請求的具體格式如下： +Name Score 上傳最新得分記錄。Name表示玩家名字，由大寫英文字母組成，不超過10個字符。Score為最多8位的正整數。 ?Name 查詢玩家排名。該玩家的得分記錄必定已經在前面上傳。 ?Index 返回自第Index名開始的最多10名玩家名字。Index必定合法，即不小於1，也不大於當前有記錄的玩家總數。輸入文件總大小不超過2M。
NOTE：用C++的fstream讀大規模數據的效率較低
Output
對於每條查詢請求，輸出相應結果。對於?Name格式的請求，應輸出一個整數表示該玩家當前的排名。對於?Index格式的請求，應在一行中依次輸出從第Index名開始的最多10名玩家姓名，用一個空格分隔。
Sample Input
20
+ADAM 1000000 加入ADAM的得分記錄
+BOB 1000000 加入BOB的得分記錄
+TOM 2000000 加入TOM的得分記錄
+CATHY 10000000 加入CATHY的得分記錄
?TOM 輸出TOM目前排名
?1 目前有記錄的玩家總數為4，因此應輸出第1名到第4名。
+DAM 100000 加入DAM的得分記錄
+BOB 1200000 更新BOB的得分記錄
+ADAM 900000 更新ADAM的得分記錄（即使比原來的差）
+FRANK 12340000 加入FRANK的得分記錄
+LEO 9000000 加入LEO的得分記錄
+KAINE 9000000 加入KAINE的得分記錄
+GRACE 8000000 加入GRACE的得分記錄
+WALT 9000000 加入WALT的得分記錄
+SANDY 8000000 加入SANDY的得分記錄
+MICK 9000000 加入MICK的得分記錄
+JACK 7320000 加入JACK的得分記錄
?2 目前有記錄的玩家總數為12，因此應輸出第2名到第11名。
?5 輸出第5名到第13名。
?KAINE 輸出KAINE的排名
Sample Output
2
CATHY TOM ADAM BOB
CATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB
WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM
【分析】我就不吐槽HN抄襲浙江的題目了。。這道題的坑爹之處是字符串的處理。如何判斷一個字符串是否出現？哈希本來是個好選擇，但是我生怕25萬的數據會被卡，只好硬生生地開了一棵字母樹。。
為了鞏固splay，全是手碼的，於是乎調了半天，囧rz。說一下如何查詢。他要找排名從K開始的10個人，我就設L=K,R=K+9。那麼我們只需在正常的查詢（可參見之前的程序）裡把一個固定的值改成一個范圍~~
還有，開始我一直T，後來一氣之下，在詢問時也找了個點splay一下，然後瞬秒出解。沒事多轉轉~~
【AC代碼】
/**************************************************************
Problem: 1862
User: jiangshibiao
Language: C++
Result: Accepted
Time:1148 ms
Memory:50828 kb
****************************************************************/
#include
#include
#define N 300005
using namespace std;
int son[N][3],Num[N][3],f[N],a[N],b[N],trie[N][27],L[N],score[N],ans[N];
char Str[N][12],opt[12];
int k,i,num,add,now,flag,tree,root,node,left,right,tot,Q,l,n,j,PRE;
void Rotate(int x,int w)
{
int y=f[x],z=f[y];
son[y][3-w]=son[x][w];
if (son[x][w]) f[son[x][w]]=y;
f[x]=z;
Num[y][3-w]=Num[x][w];
Num[x][w]+=Num[y][w]+1;
if (z)
if (son[z][1]==y) son[z][1]=x;else son[z][2]=x;
f[y]=x;son[x][w]=y;
}
inline void splay(int x)
{
int y;
while (f[x])
{
y=f[x];
if (!f[y])
{
if (x==son[y][1]) Rotate(x,2);else Rotate(x,1);continue;
}
if (y==son[f[y]][1])
{
if (x==son[y][1]) Rotate(y,2),Rotate(x,2);
else Rotate(x,1),Rotate(x,2);
}
else
{
if (x==son[y][2]) Rotate(y,1),Rotate(x,1);
else Rotate(x,2),Rotate(x,1);
}
}
root=x;
}
inline void insert(int x,int num,int add)
{
if (!x)
{
root=++node;
a[node]=add;
b[node]=num;
return;
}
if (addb[x])
{
if (!son[x][1]) son[x][1]=++node,a[node]=add,b[node]=num,f[node]=x;
else insert(son[x][1],num,add);
Num[x][1]++;
}
else
{
if (!son[x][2]) son[x][2]=++node,a[node]=add,b[node]=num,f[node]=x;
else insert(son[x][2],num,add);
Num[x][2]++;
}
}
inline void del(int x,int num,int add)
{
if (!x) return;
if (add==a[x]&&num==b[x])
{
splay(x);
int find=son[x][1],temp=son[x][2];
if (!find&&!temp){root=0;return;}
if (!find) {root=son[x][2];f[son[x][2]]=0;return;}
if (!temp) {root=son[x][1];f[son[x][1]]=0;return;}
while (son[find][2]) find=son[find][2];
f[son[x][1]]=0;splay(find);Num[find][2]+=Num[temp][1]+Num[temp][2]+1;
son[find][2]=temp;
f[temp]=find;root=find;
return;
}
if (addb[x]) del(son[x][1],num,add);
else del(son[x][2],num,add);
}
int walk(int k,int p)
{
if (p==l) {tree=k;return L[k]?L[k]:L[k]=i;}
if (trie[k][opt[p]-65]) return walk(trie[k][opt[p]-65],p+1);
trie[k][opt[p]-65]=++tot;flag=0;
return walk(tot,p+1);
}
int Kth(int x,int now)
{
if (!x) return 0;
if (add==a[x]&&num==b[x])
{
PRE=x;
return now+1+Num[x][2];
}
if (addb[x]) return Kth(son[x][1],now+Num[x][2]+1);
return Kth(son[x][2],now);
}
void Ask(int x,int now)
{
if (!x) return;
int temp=Num[x][2]+now;
if (temp>=left) Ask(son[x][2],now);
if (temp+1>=left&&temp+1<=right)
{
ans[++n]=b[x];
PRE=x;
}
if (temp+1='0'&&opt[1]<='9')
{
k=0;n=0;
for (j=1;j
【BZOJ1503】
1503: [NOI2004]郁悶的出納員
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 5542 Solved: 1968
Description
OIER公司是一家大型專業化軟件公司，有著數以萬計的員工。作為一名出納員，我的任務之一便是統計每位員工的工資。這本來是一份不錯的工作，但是令人郁悶的是，我們的老板反復無常，經常調整員工的工資。如果他心情好，就可能把每位員工的工資加上一個相同的量。反之，如果心情不好，就可能把他們的工資扣除一個相同的量。我真不知道除了調工資他還做什麼其它事情。工資的頻繁調整很讓員工反感，尤其是集體扣除工資的時候，一旦某位員工發現自己的工資已經低於了合同規定的工資下界，他就會立刻氣憤地離開公司，並且再也不會回來了。每位員工的工資下界都是統一規定的。每當一個人離開公司，我就要從電腦中把他的工資檔案刪去，同樣，每當公司招聘了一位新員工，我就得為他新建一個工資檔案。老板經常到我這邊來詢問工資情況，他並不問具體某位員工的工資情況，而是問現在工資第k多的員工拿多少工資。每當這時，我就不得不對數萬個員工進行一次漫長的排序，然後告訴他答案。好了，現在你已經對我的工作了解不少了。正如你猜的那樣，我想請你編一個工資統計程序。怎麼樣，不是很困難吧？
Input
Output
輸出文件的行數為F命令的條數加一。對於每條F命令，你的程序要輸出一行，僅包含一個整數，為當前工資第k多的員工所拿的工資數，如果k大於目前員工的數目，則輸出-1。輸出文件的最後一行包含一個整數，為離開公司的員工的總數。
Sample Input
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
Sample Output
10
20
-1
2
HINT
I命令的條數不超過100000 A命令和S命令的總條數不超過100 F命令的條數不超過100000 每次工資調整的調整量不超過1000 新員工的工資不超過100000
【分析】這道題說起來也是辛酸的歷史。首先談談如何處理增加和減少工資的問題。我傻叉地開了一個f數組。每次判斷一個splay中的結點時，他的實際權值是a[x]+f[q]-f[b[x]-1]。其中a[x]是剛進來的工資，q是現在這個詢問，b[x]是x剛進來的時候所在的詢問。（有點類似於前綴和的思想）後來網上看了一下，可以直接開一個數組記錄~~~
再說明一下如何刪除。（真是爽！）假設要刪除
【代碼】
/**************************************************************
Problem: 1503
User: jiangshibiao
Language: C++
Result: Accepted
Time:1372 ms
Memory:16040 kb
****************************************************************/
#include
#define N 300005
using namespace std;
int son[N][3],num[N][3],f[N],a[N],b[N],T[N];
char Str[N][12],opt[12],s[5];
int k,i,root,node,P,Min,q,Q,l,n,j,PRE,away;
void Rotate(int x,int w)
{
int y=f[x],z=f[y];
son[y][3-w]=son[x][w];
if (son[x][w]) f[son[x][w]]=y;
f[x]=z;
num[y][3-w]=num[x][w];
num[x][w]+=num[y][w]+1;
if (z)
if (son[z][1]==y) son[z][1]=x;else son[z][2]=x;
f[y]=x;son[x][w]=y;
}
void splay(int x)
{
while (f[x])
{
int y=f[x],z=f[y];
if (!z)
{
if (son[y][1]==x) Rotate(x,2);else Rotate(x,1);
continue;
}
if (son[z][1]==y)
{
if (son[y][1]==x) Rotate(y,2),Rotate(x,2);
else Rotate(x,1),Rotate(x,2);
}
else
{
if (son[y][2]==x) Rotate(y,1),Rotate(x,1);
else Rotate(x,2),Rotate(x,1);
}
}
root=x;
}
void insert(int x)
{
if (!x){a[++node]=P;b[node]=q;return;}
if (P=P) return Ask(son[x][2],now);
else return Ask(son[x][1],temp+1);
}
int main()
{
scanf("%d%d",&Q,&Min);
for (q=1;q<=Q;q++)
{
scanf("%s%d",s,&P);T[q]=T[q-1];
if (s[0]=='I')
{
if (P
