【算法简介】
FHQ−Treap,也称非旋 Treap,由范浩强提出。顾名思义,FHQ−Treap 就是不需要通过旋转,而是通过 split 和 merge 维护的 Treap。FHQ−Treap 与 Treap 的另外一个区别是 FHQ−Treap 可持久化。
【问题描述】
题目来源:
普通平衡树 - 洛谷P3369
普通平衡树 - AcWing253
【算法代码】
#include <bits/stdc++.h>
using namespace std;
const int maxn=500005;
int ch[maxn][2],val[maxn],pri[maxn],cnt[maxn],id;
int read() { //fast read
int x=0,f=1;
char c=getchar();
while(c<'0' || c>'9') { //!isdigit(c)
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') { //isdigit(c)
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void update(int x) {
cnt[x]=1+cnt[ch[x][0]]+cnt[ch[x][1]];
}
int new_node(int v) {
cnt[++id]=1;
val[id]=v;
pri[id]=rand();
return id;
}
int merge(int x,int y) {
if (!x || !y) return x+y;
if (pri[x]<pri[y]) {
ch[x][1]=merge(ch[x][1],y);
update(x);
return x;
} else {
ch[y][0]=merge(x,ch[y][0]);
update(y);
return y;
}
}
void split(int cur,int k,int &x,int &y) {
if (!cur) x=y=0;
else {
if (val[cur]<=k)
x=cur,split(ch[cur][1],k,ch[cur][1],y);
else
y=cur,split(ch[cur][0],k,x,ch[cur][0]);
update(cur);
}
}
int kth(int cur,int k) {
while(1) {
if (k<=cnt[ch[cur][0]])
cur=ch[cur][0];
else if (k==cnt[ch[cur][0]]+1)
return cur;
else
k-=cnt[ch[cur][0]]+1,cur=ch[cur][1];
}
}
int main() {
int T,opt,x,y,z,a,b,root=0;
T=read();
while(T--) {
opt=read(),a=read();
if (opt==1) {
split(root,a,x,y);
root=merge(merge(x,new_node(a)),y);
} else if (opt==2) {
split(root,a,x,z);
split(x,a-1,x,y);
y=merge(ch[y][0],ch[y][1]);
root=merge(merge(x,y),z);
} else if (opt==3) {
split(root,a-1,x,y);
printf("%d\n",cnt[x]+1);
root=merge(x,y);
} else if (opt==4)
printf("%d\n",val[kth(root,a)]);
else if (opt==5) {
split(root,a-1,x,y);
printf("%d\n",val[kth(x,cnt[x])]);
root=merge(x,y);
} else {
split(root,a,x,y);
printf("%d\n",val[kth(y,1)]);
root=merge(x,y);
}
}
return 0;
}
/*
in:
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
out:
106465
84185
492737
*/
【参考文献】
http://www.yhzq-blog.cc/fhq-treap%E6%80%BB%E7%BB%93/
https://www.luogu.com.cn/problem/P3369
https://www.acwing.com/problem/content/255/
https://www.acwing.com/blog/content/4455/
https://www.acwing.com/problem/content/description/268/