Hihocoder 1329 平衡树·Splay（平衡树）
Description
小Ho：小Hi，上一次你跟我讲了Treap，我也实现了。但是我遇到了一个关键的问题。
小Hi：怎么了？
小Ho：小Hi你也知道，我平时运气不太好。所以这也反映到了我写的Treap上。
小Hi：你是说你随机出来的权值不太好，从而导致结果很差么？
小Ho：就是这样，明明一样的代码，我的Treap运行结果总是不如别人。小Hi，有没有那种没有随机因素的平衡树呢？
小Hi：当然有了，这次我就跟你讲讲一种叫做Splay的树吧。而且Splay树能做到的功能比Treap要更强大哦。
小Ho：那太好了，你快告诉我吧！
Input
第1行：1个正整数n，表示操作数量，100≤n≤200,000
第2..n+1行：可能包含下面3种规则：
1个字母'I'，紧接着1个数字k，表示插入一个数字k到树中，1≤k≤1,000,000,000，保证每个k都不相同
1个字母'Q'，紧接着1个数字k。表示询问树中不超过k的最大数字
1个字母'D'，紧接着2个数字a,b，表示删除树中在区间[a,b]的数。
Output
若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解
Sample Input
6
I 1
I 2
I 3
Q 4
D 2 2
Q 2
Sample Output
3
1
Http
Hihocoder:https://hihocoder.com/problemset/problem/1329
Source
平衡树，Splay
解决思路
平衡树Splay
待填坑
（可以参考yyb的教程：http://www.cnblogs.com/cjyyb/p/7499020.html）
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxN=10000101;
const int inf=2147483647;
class SplayData
{
public:
int fa,ch[2],key,cnt,size;
SplayData()
{
ch[0]=ch[1]=0;
cnt=0;
size=0;
}
};
class SplayTree
{
public:
int cnt;
int root;
SplayData S[maxN];
SplayTree()
{
root=0;
cnt=0;
Insert(-inf);
Insert(inf);
}
void Insert(int x)
{
int now=root;
int nowf=0;
while ((now!=0)&&(S[now].key!=x))
{
nowf=now;
now=S[now].ch[x>S[now].key];
}
if (now==0)
{
cnt++;
now=cnt;
S[cnt].fa=nowf;
S[cnt].cnt=S[cnt].size=1;
S[cnt].key=x;
if (nowf!=0)
S[nowf].ch[x>S[nowf].key]=cnt;
if (root==0)
root=1;
}
else
S[now].cnt++;
Splay(now,0);
return;
}
bool Find(int x)
{
int now=root;
if (root==0)
return 0;
while ((S[now].ch[x>S[now].key]!=0)&&(x!=S[now].key))
{
//cout<<now<<endl;
now=S[now].ch[x>S[now].key];
}
//cout<<now<<endl;
Splay(now,0);
if (x!=S[now].key)
return 0;
return 1;
}
void Rotate(int x)
{
int y=S[x].fa;
int z=S[y].fa;
int k1=S[y].ch[1]==x;
int k2=S[z].ch[1]==y;
S[z].ch[k2]=x;
S[x].fa=z;
S[y].ch[k1]=S[x].ch[k1^1];
S[S[x].ch[k1^1]].fa=y;
S[x].ch[k1^1]=y;
S[y].fa=x;
return;
}
void Splay(const int x,int goal)
{
while (S[x].fa!=goal)
{
int y=S[x].fa;
int z=S[y].fa;
if (z!=goal)
((S[z].ch[0]==y)^(S[y].ch[0]==x))?Rotate(x):Rotate(y);
Rotate(x);
}
if (goal==0)
root=x;
return;
}
int Next(int x,int opt)
{
Find(x);
int now=root;
if ((S[now].key<x)&&(opt==0))
return now;
if ((S[now].key>x)&&(opt==1))
return now;
now=S[now].ch[opt];
while (S[now].ch[opt^1]!=0)
now=S[now].ch[opt^1];
return now;
}
void DeleteRange(int l,int r)
{
Insert(l);
Insert(r);
int prep=Next(l,0);
int nex=Next(r,1);
Splay(prep,0);
Splay(nex,prep);
S[nex].ch[0]=0;
return;
}
void Outp()
{
cout<<"SplaySize:"<<cnt<<endl;
cout<<"Root:"<<root<<endl;
for (int o=1;o<=cnt;o++)
cout<<o<<" "<<S[o].key<<" "<<S[o].ch[0]<<" "<<S[o].ch[1]<<" "<<S[o].fa<<endl;
return;
}
};
int n;
SplayTree SP;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
char opt;
opt=getchar();
while ((opt!='I')&&(opt!='Q')&&(opt!='D'))
opt=getchar();
if (opt=='I')
{
int k;
scanf("%d",&k);
SP.Insert(k);
}
if (opt=='Q')
{
int k;
scanf("%d",&k);
if (SP.Find(k))
{
printf("%d
",k);
continue;
}
int prep=SP.Next(k,0);
printf("%d
",SP.S[prep].key);
}
if (opt=='D')
{
int l,r;
scanf("%d%d",&l,&r);
SP.DeleteRange(l,r);
}
//SP.Outp();
}
return 0;
}