FHQ-Treap
依赖分裂合并的tree+heap（听起来像ODT）
核心操作：
分裂：
一种是按权值分裂，一种是按排名分裂
根据粉兔的博客，发现权值操作都可以通过rank转化为排名
于是乎只打排名了
当前需要的排名比左儿子数量大，即左子树和其本身归为第一颗分裂树，进入右子树
反之同理，上述过程可以用BST性质解释
通过BST的性质，也可以知道传下来的引用就是两颗子树预备插入节点
合并：
treap以随机化id来构造期望平衡的BST，合并的时候第一颗树的所有节点一定比第二颗树小，
于是合并时候只需考虑合并节点的id
左子树id小，将右子树挂载到右儿子下，右子树id小，则将左子树挂载到右子树左儿子上，可以保证满足BST性质
通过这两个操作可以完成各种操作，并且本身支持区间（分裂出来就是一个一个一个区间啊啊啊啊啊啊啊）和可持续化。
基本操作：
查询x的排名 :
由于没有权值分裂，所以需要递归查找，通过BST的性质，每次递归进入一个子树
注意：这样查询是查询到<=v的最末尾
插入 :
构建一个节点，然后查询权值所在排名，将树分裂成两颗，将这两颗树与节点合并
删除 :
将树分裂成v,v-1三颗，删除中间等于v的那棵
如果只删除一个的话，可以合并中间那棵的左右子树，将根节点丢掉
然后再合并起来
垃圾回收？不存在的（）
第k小 :
直接分裂成k,k-1三颗子树，输出中间那棵，再全部合并起来
前驱 :
kth(rank(root,v-1))
后继 :
kth(rank(root,v)+1)
注意：后继不可以查询rank(root,v+1),很可能后继比v+1大，rank又是查找到<=v+1的最末尾
由于前驱一定<=v-1，所以可以直接查询rank(root,v-1)
注意事项：
查询一个数的排名一定要查询rank(root,v-1)+1,不然会查到相同元素的最末尾去
code:
点击查看代码
#include<stdio.h>
#include<time.h>
#include <stdlib.h>
#define MAXN 114514
using namespace std;
const int P=2147483647;
class node{
public:
int w,siz,id,l,r;
}t[MAXN];
int tot,root,op,tx,n,seed=233;
int Rand(){
return seed=(int)(seed*482711LL%P);
}
int build(int v){
t[++tot].w=v;
t[tot].siz=1;
t[tot].l=t[tot].r=0;
t[tot].id=Rand();
return tot;
}
void update(int k){
t[k].siz=t[t[k].l].siz+t[t[k].r].siz+1;
}
void ssplit(int k,int &x,int &y,int s)
{
if(!k)//空节点
{
x=y=0;
return;
}
if(s>t[t[k].l].siz)
x=k,//将本节点挂载到第一颗子树
ssplit(t[k].r,t[k].r,y,s-t[t[k].l].siz-1);//减去左子树大小+1后进入右儿子,因为也要丢掉这个节点
else y=k,ssplit(t[k].l,x,t[k].l,s);//进入左儿子
update(k);//更新节点信息
}
int merge(int x,int y)
{
if(!x || !y) return x^y;//有节点为空
if(t[x].id<t[y].id)
{
t[x].r=merge(t[x].r,y);//把第一个节点的右儿子与第二个节点合并
update(x);//更新节点信息
return x;//返回新的根
}
else{
t[y].l=merge(x,t[y].l);//把第一个节点和第二个节点的左儿子合并
update(y);//更新节点信息
return y;//返回新的根
}
}
int rank(int k,int v){
if(!k)return 0;
if(v<t[k].w){
return rank(t[k].l,v);
}
else return t[t[k].l].siz+rank(t[k].r,v)+1;
}
void insert(int v){
int r=rank(root,v);
int r1=0,r2=0,r3=build(v);
ssplit(root,r1,r2,r);
root=merge(merge(r1,r3),r2);
}
void del(int v){
int r=rank(root,v);
int r1=0,r2=0,r3=0;
ssplit(root,r1,r2,r);
ssplit(r1,r1,r3,r-1);
r3=merge(t[r3].l,t[r3].r);
root=merge(merge(r1,r3),r2);
}
int kth(int k){
int r1=0,r2=0,r3=0;
ssplit(root,r1,r2,k);
ssplit(r1,r1,r3,k-1);
int ans=t[r3].w;
root=merge(merge(r1,r3),r2);
return ans;
}
int main(){
srand(time(NULL));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&op,&tx);
if(op==1){
insert(tx);
}
else if(op==2){
del(tx);
}
else if(op==3){
int ans=rank(root,tx-1)+1;
//if(tx==899873)puts("!!!");
//if(ans==617)printf("%d",tx);
printf("%d\n",ans);
}
else if(op==4){
printf("%d\n",kth(tx));
}
else if(op==5){//前に駆ける
printf("%d\n",kth(rank(root,tx-1)));
}
else if(op==6){
printf("%d\n",kth(rank(root,tx)+1));
}
}
return 0;
}