描述
小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=100010; struct treapdata { int ch[2],size,cnt,val,rnd; treapdata(){ ch[0]=ch[1]=0; size=cnt=val=rnd=0; } }; struct Treap { int root,cnt; Treap() { root=cnt=0; } treapdata S[maxn]; void update(int now) { S[now].size=S[now].cnt+S[S[now].ch[0]].size+S[S[now].ch[1]].size; } void rotate(int &x,int t) { int y=S[x].ch[t]; S[x].ch[t]=S[y].ch[1-t]; S[y].ch[1-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=1; S[x].rnd=rand(); S[x].ch[0]=S[x].ch[1]=0; } update(x); } int querykth(int now,int k)//第k小 { if(k<=S[S[now].ch[0]].size) return querykth(S[now].ch[0],k); k=k-S[S[now].ch[0]].size-S[now].cnt; if(k<=0) return S[now].val; return querykth(S[now].ch[1],k); } }; Treap Tp; int main() { int k,n; char opt[2]; scanf("%d",&n); while(n--){ scanf("%s",opt); scanf("%d",&k); if(opt[0]=='I') Tp.insert(Tp.root,k); else printf("%d ",Tp.querykth(Tp.root,k)); } return 0; }