题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3224
————————————————————————————————————————————
3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 12058 Solved: 5154
[Submit][Status][discuss]
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
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
Source
平衡树
————————————————————————————————————————————
这两天不知怎地 一点思考能力都没有。 于是学了学Splay
其实Splay很好懂 只要知道平衡树的左旋和右旋操作，知道作用是吧一棵树做矮，就是不使它的某一条链变成。
本质还是一颗二叉树，只不过多了伸展的操作，也就是能通过左旋，右旋降低树高，保证某些操作总是在O(logn)的 不会变成O(n)。
附模板
————————————————————————————————————
#include <bits/stdc++.h>
using namespace std;
const int N = 100000+7;
int root,tot;
int father[N],data[N],cnt[N],value[N];
int son[N][3];
inline void Rotate(int x,int w){
int y=father[x];
cnt[y]=cnt[y]-cnt[x]+cnt[son[x][w]];
cnt[x]=cnt[x]-cnt[son[x][w]]+cnt[y];
son[y][3-w]=son[x][w];
if(son[x][w]) father[son[x][w]]=y;
father[x]=father[y];
if(father[y]){
if(y==son[father[y]][1]) son[father[y]][1]=x;
else son[father[y]][2]=x;
}
father[y]=x;
son[x][w]=y;
}
inline void splay(int x){
int y;
while(father[x]){
y=father[x];
if(!father[y]){
if(x==son[y][1]) Rotate(x,2);
else Rotate(x,1);
}
else{
if(y==son[father[y]][1]){
if(x==son[y][1]) Rotate(y,2),Rotate(x,2);
else Rotate(x,1),2);
}
else {
if(x==son[y][2]) Rotate(y,1);
else Rotate(x,1);
}
}
}
root = x;
return ;
}
inline int Search(int x,int w){
while(data[x]!=w){
if(w==data[x]) return x;
if(w<data[x]) {
if(!son[x][1]) break;
x = son[x][1];
}
else {
if(!son[x][2]) break;
x = son[x][2];
}
}
return x;
}
inline void Insert(int w){
int k,kk;bool flag;
if(!tot){
tot=1;
father[1]=0;cnt[1]=1;data[1]=w;root=1;value[1]=1;
return ;
}
k = Search(root,w);
if(data[k]==w){
value[k]++;kk=k;
flag = true;
}
else{
tot++;
data[tot]=w;
father[tot]=k;
cnt[tot]=1;
value[tot]=1;
if(data[k]>w) son[k][1]=tot;
else son[k][2]=tot;
flag = false;
}
while(k){
cnt[k]++;k=father[k];
}
if(flag) splay(kk);else splay(tot);
}
inline int Extreme(int x,int w){
const int lala[3]={0,2147483647,-2147483647};
int k=Search(x,lala[w]),tmp;
tmp = data[k];
splay(k);
return tmp;
}
inline void del(int x){
int k=Search(root,x),y;
splay(k);
if(data[k]==x){
if(value[k]>1){
value[k]--;
cnt[k]--;
}
else if(!son[k][1]){
y=son[k][2];
son[k][2]=0;
cnt[k]=0;
data[k]=0;
value[k]=0;
root = y;
father[root]=0;
}
else {
father[son[k][1]]=0;
y=Extreme(son[k][1],1);
son[root][2]=son[k][2];
cnt[root]=cnt[root]+cnt[son[k][2]];
if(son[root][2])father[son[root][2]]=root;
data[k]=0;son[k][1];son[k][2]=0;
value[k]=0;
}
}
}
inline int pred(int x){
int k = Search(root,x);
splay(k);
if(data[k]<x) return data[k];
return Extreme(son[k][1],1);
}
inline int succ(int x){
int k = Search(root,x);
splay(k);
if(data[k]>x) return data[k];
return Extreme(son[k][2],2);
}
inline int kth(int x,int w){
int i=root,tmp;
while(!((x>=cnt[son[i][w]]+1)&&(x<=cnt[son[i][w]]+value[i]))&&i){
if(x>cnt[son[i][w]]+value[i]){
x = x - cnt[son[i][w]]-value[i];
i = son[i][3-w];
}
else i = son[i][w];
}
tmp = i;splay(i);
return tmp;
}
inline int findnum(int x){
int k = Search(root,x);splay(k);
root = k;
return cnt[son[k][1]]+1;
}
int main(){
int n,op,x;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&op,&x);
if(1==op) Insert(x);
else if(2==op) del(x);
else if(3==op) printf("%d\n",findnum(x));
else if(4==op) printf("%d\n",data[kth(x,1)]);
else if(5==op) printf("%d\n",pred(x));
else if(6==op) printf("%d\n",succ(x));
}
return 0;
}