正文
HihoCoder1337 动态第k大（treap）
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
描述
小Ho：小Hi，之前你不是讲过Splay和Treap么，那么还有没有更简单的平衡树呢？
小Hi：但是Splay和Treap不是已经很简单了么？
小Ho：是这样没错啦，但是Splay和Treap和原来的二叉搜索树相比都有很大的改动，我有点记不住。
小Hi：这样啊，那我不妨再给你讲解一个新的平衡树算法好了。和二叉搜索树相比，它只需要修改insert函数，就可以做到高度的平衡。
小Ho：好，我就喜欢这样的！
输入
第1行：1个正整数n，表示操作数量，10≤n≤100,000
第2..n+1行：每行1个字母c和1个整数k：
若c为'I'，表示插入一个数字k到树中，-1,000,000,000≤k≤1,000,000,000
若c为'Q'，表示询问树中第k小数字，保证1≤k≤树的节点数量
输出
若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解
样例输入
5
I 3
I 2
Q 1
I 5
Q 2
样例输出
2
3
先结合Treap和这两天写的结构体试一试。
其中
1，rotate函数没差。
2，update在儿子有变化后都要更新。
3，insert有‘&’符号，不需要特殊处理root=0的情况
4，查询kth时注意边界即可推进。
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
const int maxn=;
struct treapdata
{
int ch[],size,cnt,val,rnd;
treapdata(){
ch[]=ch[]=;
size=cnt=val=rnd=;
}
};
struct Treap
{
int root,cnt;
Treap()
{
root=cnt=;
}
treapdata S[maxn];
void update(int now)
{
S[now].size=S[now].cnt+S[S[now].ch[]].size+S[S[now].ch[]].size;
}
void rotate(int &x,int t)
{
int y=S[x].ch[t];
S[x].ch[t]=S[y].ch[-t];
S[y].ch[-t]=x;
update(x);
update(y);
x=y;//！莫忘
}
void insert(int &x,int k)
{
if(x){
if(S[x].val==k) S[x].cnt++;
else{
int t=S[x].val<k;
insert(S[x].ch[t],k);
if(S[S[x].ch[t]].rnd<S[x].rnd) rotate(x,t);
}
}
else{
x=++cnt;
S[x].val=k;
S[x].cnt=;
S[x].rnd=rand();
S[x].ch[]=S[x].ch[]=;
}
update(x);
}
int querykth(int now,int k)//第k小
{
if(k<=S[S[now].ch[]].size) return querykth(S[now].ch[],k);
k=k-S[S[now].ch[]].size-S[now].cnt;
if(k<=) return S[now].val;
return querykth(S[now].ch[],k);
}
};
Treap Tp;
int main()
{
int k,n;
char opt[];
scanf("%d",&n);
while(n--){
scanf("%s",opt);
scanf("%d",&k);
if(opt[]=='I') Tp.insert(Tp.root,k);
else printf("%d\n",Tp.querykth(Tp.root,k));
}
return ;
}
