本文内容部分转自某大佬博客：https://blog.csdn.net/CABI_ZGX/article/details/79963427
例题：https://www.luogu.org/problemnew/show/P3369#sub
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入 x 数
- 删除 x 数(若有多个相同的数，因只删除一个)
- 查询 x 数的排名(排名定义为比当前数小的数的个数 +1 。若有多个相同的数，因输出最小的排名)
- 查询排名为 x 的数
- 求 x 的前驱(前驱定义为小于 x ，且最大的数)
- 求 x 的后继(后继定义为大于 x ，且最小的数)
输入输出格式
输入格式：
第一行为 n ，表示操作的个数,下面 n 行每行有两个数 opt 和 x ，opt 表示操作的序号( 1≤opt≤6 )
输出格式：
对于操作 3,4,5,6 每行输出一个数，表示对应答案
看题目就知道Treap当然是可以的，考虑fhq-treap
fhq-treap的最大特点，不需要不需要不需要旋转！！！这是棵不考旋转保持平衡的平衡树
不管怎么样，我们要让它是平衡的。好的其实有些除旋转之外的神奇的操作是有效的，下面来讲一讲。
对于随机数我们维护小根堆；对于权值左儿子的权值小于当前节点的权值，右儿子的权值大于当前节点的权值
Mergy
merge就是把两个treap合成一个，是一个递归的过程。首先明确fhq-treap的平衡条件是他的附加权值，那么只需要比较他们的附加权值大小判断在左树还是右树即可。
注意x树里的所有点的权值小于y树里的所有点的权值
inline int mergy(int x,int y)
{
if (!x||!y) return x|y;
if (a[x].rnd<a[y].rnd)
{
a[x].son[1]=mergy(a[x].son[1],y);
update(x);
return x;
}
else
{
a[y].son[0]=mergy(x,a[y].son[0]);
update(y);
return y;
}
}
Split
split是把一颗treap分开两个树的操作，也是一个递归的过程。有两种分法，一种是按权值分，一种是按size（子树大小）分。
按权值分（注意这时候权值小于等于 k的节点都在左树中，大于k的都在右树中）
void split(int now,int k,int &x,int &y)
{
if (!now)
{
x=y=0;
return;
}
if (k>=a[now].dat)
{
x=now;
split(a[now].son[1],k,a[now].son[1],y);
}
else
{
y=now;
split(a[now].son[0],k,x,a[now].son[0]);
}
update(now);
return;
}
按size分
void split(int now,int k,int &x,int &y)
{
if(!now) x=y=0;
else
{
update(now);
if (k<=tr[tr[now].son[0]].size)
y=now,split(tr[now].son[0],k,x,tr[now].son[0]);
else
x=now,split(tr[now].son[1],k-tr[tr[now].son[0]].size-1,tr[now].son[1],y);
update(now);
}
}
New，建立新的节点
int New(int x)
{
tot++;
a[tot].dat=x;a[tot].rnd=rand();a[tot].size=1;
return tot;
}
找kth的节点的权值
int kth(int now,int k)
{
while (1)
{
if (k<=a[a[now].son[0]].size) now=a[now].son[0];
else
{
if (k==a[a[now].son[0]].size+1) return now;
else
{
k=k-(a[a[now].son[0]].size+1);
now=a[now].son[1];
}
}
}
}
Insert
插入一个权值为t节点，那么只需要以t为权值split整棵树，然后New(t)在merge回去
split(root,t,x,y);
root=mergy(mergy(x,New(t)),y);
Del
删除权值为t的点，先把整颗树以t为权值split成两棵树x,z,再把x树按照t-1分成x,y。这时候值为t的点一定为y的根，那么我们把y的两个子儿子merge起来,再把他们重新merge起来得到一个新的树，这颗树就去除掉了t。
split(root,t,x,z);
split(x,t-1,x,y);
y=mergy(a[y].son[0],a[y].son[1]);
root=mergy(mergy(x,y),z);
FindRank
找值为t的节点排名，就把整棵树以t-1为权值split，那么小于t的节点全在左树内，输出左树的size即可
precursor
找前驱就把整棵树按t-1为权值split开，此时小于等于t的数全在左树里，在左树里找到排名为（左树的size）的节点权值即可。
split(root,t-1,x,y);
printf("%d
",a[kth(x,a[x].size)].dat);
root=mergy(x,y);
successor
找后继是相同的，把整棵树按t为权值split开，此时右树排名第一的数就是后继
split(root,t,x,y);
printf("%d
",a[kth(y,1)].dat);
root=mergy(x,y);
fhq-treap代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<time.h>
using namespace std;
const int maxn=1e5+15;
int n,tot,root;
struct fhq
{
int son[2];
int rnd,dat,size;
}a[maxn];
inline int read()
{
char ch=getchar();
int s=0,f=1;
while (!(ch>='0'&&ch<='9')) {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
inline void update(int x)
{
a[x].size=a[a[x].son[0]].size+a[a[x].son[1]].size+1;
return;
}
int New(int x)
{
tot++;
a[tot].dat=x;a[tot].rnd=rand();a[tot].size=1;
return tot;
}
inline int mergy(int x,int y)
{
if (!x||!y) return x|y;
if (a[x].rnd<a[y].rnd)
{
a[x].son[1]=mergy(a[x].son[1],y);
update(x);
return x;
}
else
{
a[y].son[0]=mergy(x,a[y].son[0]);
update(y);
return y;
}
}
void split(int now,int k,int &x,int &y)
{
if (!now)
{
x=y=0;
return;
}
if (k>=a[now].dat)
{
x=now;
split(a[now].son[1],k,a[now].son[1],y);
}
else
{
y=now;
split(a[now].son[0],k,x,a[now].son[0]);
}
update(now);
return;
}
int kth(int now,int k)
{
while (1)
{
if (k<=a[a[now].son[0]].size) now=a[now].son[0];
else
{
if (k==a[a[now].son[0]].size+1) return now;
else
{
k=k-(a[a[now].son[0]].size+1);
now=a[now].son[1];
}
}
}
}
int main()
{
srand(time(0));
n=read();
while (n--)
{
int opt=read(),t=read();
int x,y,z;
if (opt==1)
{
split(root,t,x,y);
root=mergy(mergy(x,New(t)),y);
}
if (opt==2)
{
split(root,t,x,z);
split(x,t-1,x,y);
y=mergy(a[y].son[0],a[y].son[1]);
root=mergy(mergy(x,y),z);
}
if (opt==3)
{
split(root,t-1,x,y);
printf("%d
",a[x].size+1);
root=mergy(x,y);
}
if (opt==4)
{
int k=kth(root,t);
printf("%d
",a[k].dat);
}
if (opt==5)
{
split(root,t-1,x,y);
printf("%d
",a[kth(x,a[x].size)].dat);
root=mergy(x,y);
}
if (opt==6)
{
split(root,t,x,y);
printf("%d
",a[kth(y,1)].dat);
root=mergy(x,y);
}
}
return 0;
}
Treap代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+15;
const int inf=1e9+7;
int n,m,tot,root;
struct TREAP
{
int l,r;
int val,dat;
int cnt,size;
}a[maxn];
inline void read(int &x)
{
char ch=getchar();
int s=0,f=1;
while (!(ch>='0'&&ch<='9')) {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
x=s*f;
}
int New(int val){
a[++tot].val=val;
a[tot].cnt=a[tot].size=1;
a[tot].dat=rand();
return tot;
}
void update(int p){
a[p].size=a[a[p].l].size+a[p].cnt+a[a[p].r].size;
}
void build()
{
New(-inf);New(inf);
root=1;a[1].r=2;
update(root);
}
int get_rank_by_val(int p,int val)
{
if (!p) return 0;
if (val==a[p].val) return a[a[p].l].size+1;
if (val<a[p].val) return get_rank_by_val(a[p].l,val);
return a[a[p].l].size+a[p].cnt+get_rank_by_val(a[p].r,val);
}
int get_val_by_rank(int p,int rank)
{
if (!p) return inf;
if (a[a[p].l].size>=rank) return get_val_by_rank(a[p].l,rank);
if (a[a[p].l].size+a[p].cnt>=rank) return a[p].val;
return get_val_by_rank(a[p].r,rank-a[a[p].l].size-a[p].cnt);
}
void zig(int &p)
{
int q=a[p].l;
a[p].l=a[q].r;a[q].r=p;p=q;
update(a[p].r);update(p);
}
void zag(int &p)
{
int q=a[p].r;
a[p].r=a[q].l;a[q].l=p;p=q;
update(a[p].l);update(p);
}
void insert(int &p,int val)
{
if (!p){
p=New(val);
return;
}
if (val==a[p].val){
a[p].cnt++;update(p);
return;
}
if (val<a[p].val){
insert(a[p].l,val);
if (a[p].dat<a[a[p].l].dat) zig(p);
}
else {
insert(a[p].r,val);
if (a[p].dat<a[a[p].r].dat) zag(p);
}
update(p);
}
int getpre(int val)
{
int ans=1;
int p=root;
while (p){
if (val==a[p].val){
if (a[p].l>0) {
p=a[p].l;
while (a[p].r>0) p=a[p].r;
ans=p;
}
break;
}
if (a[p].val<val&&a[p].val>a[ans].val) ans=p;
if (val<a[p].val) p=a[p].l;else p=a[p].r;
}
return a[ans].val;
}
int getnext(int val)
{
int ans=2;
int p=root;
while (p){
if (val==a[p].val){
if (a[p].r>0){
p=a[p].r;
while (a[p].l>0) p=a[p].l;
ans=p;
}
break;
}
if (a[p].val>val&&a[p].val<a[ans].val) ans=p;
if (val<a[p].val) p=a[p].l;else p=a[p].r;
}
return a[ans].val;
}
void remove(int &p,int val)
{
if (!p) return;
if (val==a[p].val){
if (a[p].cnt>1) {
a[p].cnt--;update(p);
return;
}
if (a[p].l||a[p].r){
if (a[p].r==0||a[a[p].l].dat>a[a[p].r].dat){
zig(p);remove(a[p].r,val);
}
else {
zag(p);remove(a[p].l,val);
}
update(p);
}
else p=0;
return;
}
if (val<a[p].val) remove(a[p].l,val);else remove(a[p].r,val);
update(p);
}
int main()
{
int opt;
build();
read(n);
while (n--)
{
read(opt);int x;
read(x);
if (opt==1) insert(root,x);
if (opt==2) remove(root,x);
if (opt==3) printf("%d
",get_rank_by_val(root,x)-1);
if (opt==4) printf("%d
",get_val_by_rank(root,x+1));
if (opt==5) printf("%d
",getpre(x));
if (opt==6) printf("%d
",getnext(x));
}
return 0;
}
其实还有vector写法：
#include<bits/stdc++.h>
using namespace std;
int n,opt,x;
vector <int> p;
int main()
{
p.reserve(100001+15);
scanf("%d",&n);
while (n--)
{
scanf("%d%d",&opt,&x);
if (opt==1) p.insert(lower_bound(p.begin(),p.end(),x),x);
if (opt==2) p.erase(lower_bound(p.begin(),p.end(),x));
if (opt==3) printf("%d
",lower_bound(p.begin(),p.end(),x)-p.begin()+1);
if (opt==4) printf("%d
",p[x-1]);
if (opt==5)printf("%d
",p[lower_bound(p.begin(),p.end(),x)-p.begin()-1]);
if (opt==6) printf("%d
",p[upper_bound(p.begin(),p.end(),x)-p.begin()]);
}
return 0;
}