【前言】快要省选二试了。上次去被虐出翔了~~这次即便是打酱油，也要打出风采！于是暂停新东西的学习，然后开始复习以前的知识，为骗分做准备。PS：区间翻转的暂时跳过，就算学了也来不及巩固了。
【BZOJ3224】
3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
101 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
10646584185
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
C