fhq_treap（无旋 treap）
参考：远航之曲的博客。
感觉比较意识流。
核心思想是平衡树分裂和合并。
类似于 Splay 把区间分离出来，fhq_treap 可以把平衡树进行分裂来提取需要的区间，再通过合并平衡树来维持树高（即堆性质）。这样不仅可以做到维护区间，还免去了旋转操作，代码较为简单。
split & merge & kth
inline void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
inline void split(int u,int k,int &x,int &y){
if(!u) x=y=0;
else{
if(val[u]<=k) x=u,split(ch[u][1],k,ch[u][1],y);
else y=u,split(ch[u][0],k,x,ch[u][0]);
pushup(u);
}
}
我们把一棵平衡树所有权值不大于 $k$ 的结点分成一棵树，其他结点分成另一颗树。如果一个结点权值不大于 $k$，其左子树也一定不大于 $k$，可以直接把该节点连着左子树并入其中一棵树，我们只需要接着考虑右子树。如果其权值大于 $k$ 同理。
pushup 操作可以用来更新子树大小等信息。
有时候也可以考虑将前 $k$ 小的结点分成一棵树，即按照数量来分，详见「对于区间的操作」部分。
inline int merge(int x,int y){
if(!x||!y) return x+y;
if(rnd[x]<rnd[y]){
ch[x][1]=merge(ch[x][1],y);
pushup(x);return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
pushup(y);return y;
}
}
合并操作就类似于堆的合并，由于堆的权值是随机的，所以暴力合并即可。
inline int kth(int u,int k){
while(1){
if(k<=siz[ch[u][0]]) u=ch[u][0];
else if(k==siz[ch[u][0]]+1) return u;
else k-=siz[ch[u][0]]+1,u=ch[u][1];
}
}
kth 操作用来查询查询排名为 $k$ 的数，这个操作有时可以很好地搭配上述操作。
一些基础操作不多赘述，有需要的可以看下边的完整代码的普通平衡树部分。
对于区间的操作
类似于 Splay，我们可以维护一个序列，然后每次对于区间操作时只需要把所需要的区间 split 出来再对整棵树进行操作（例如打标记）即可。为了找出区间，我们需要对于 split 操作进行一些修改，即从按权值分裂为分裂前 $k$ 个结点。
inline void split(int u,int k,int &x,int &y){
if(!u) x=y=0;
else{
pushdown(u);
if(siz[ch[u][0]]<k) x=u,split(ch[u][1],k-siz[ch[u][0]]-1,ch[u][1],y);
else y=u,split(ch[u][0],k,x,ch[u][0]);
pushup(u);
}
}
用这样的办法可以解决区间翻转等普通 treap 无法实现的问题。详见下方完整代码的文艺平衡树部分。
完整代码
Luogu3369 【模板】普通平衡树
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int ch[N][2],val[N],rnd[N],siz[N],root,cnt;
int newnode(int x){
siz[++cnt]=1;
val[cnt]=x;
rnd[cnt]=rand();
return cnt;
}
inline void pushup(int x){
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
inline int merge(int x,int y){
if(!x||!y) return x+y;
if(rnd[x]<rnd[y]){
ch[x][1]=merge(ch[x][1],y);
pushup(x);return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
pushup(y);return y;
}
}
inline void split(int u,int k,int &x,int &y){
if(!u) x=y=0;
else{
if(val[u]<=k) x=u,split(ch[u][1],k,ch[u][1],y);
else y=u,split(ch[u][0],k,x,ch[u][0]);
pushup(u);
}
}
inline int kth(int u,int k){
while(1){
if(k<=siz[ch[u][0]]) u=ch[u][0];
else if(k==siz[ch[u][0]]+1) return u;
else k-=siz[ch[u][0]]+1,u=ch[u][1];
}
}
int Q;
int main(){
srand(time(0));scanf("%d",&Q);
while(Q--){
int opt,a,x,y,z;
scanf("%d%d",&opt,&a);
if(opt==1){
split(root,a,x,y);
root=merge(merge(x,newnode(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",siz[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,siz[x])]);
root=merge(x,y);
}
else if(opt==6){
split(root,a,x,y);
printf("%d\n",val[kth(y,1)]);
root=merge(x,y);
}
}
return 0;
}
Luogu3391 【模板】文艺平衡树
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int ch[N][2],val[N],rnd[N],siz[N],root,cnt;
bool tag[N];
int newnode(int x){
siz[++cnt]=1;
val[cnt]=x;
rnd[cnt]=rand();
return cnt;
}
inline void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
inline void pushdown(int x){
if(!tag[x]) return;
swap(ch[x][0],ch[x][1]);
if(ch[x][0]) tag[ch[x][0]]^=1;
if(ch[x][1]) tag[ch[x][1]]^=1;
tag[x]=0;
}
inline int merge(int x,int y){
if(!x||!y) return x+y;
if(rnd[x]<rnd[y]){
pushdown(x);
ch[x][1]=merge(ch[x][1],y);
pushup(x);return x;
}
else{
pushdown(y);
ch[y][0]=merge(x,ch[y][0]);
pushup(y);return y;
}
}
inline void split(int u,int k,int &x,int &y){
if(!u) x=y=0;
else{
pushdown(u);
if(siz[ch[u][0]]<k) x=u,split(ch[u][1],k-siz[ch[u][0]]-1,ch[u][1],y);
else y=u,split(ch[u][0],k,x,ch[u][0]);
pushup(u);
}
}
inline void get(int u){
if(!u) return;
pushdown(u);
get(ch[u][0]);
printf("%d ",val[u]);
get(ch[u][1]);
}
int n,m;
int main(){
srand(time(0));scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) root=merge(root,newnode(i));
for(int i=1;i<=m;i++){
int l,r,x,y,z;scanf("%d%d",&l,&r);
split(root,l-1,x,y);split(y,r-l+1,y,z);
tag[y]^=1;
merge(merge(x,y),z);
}
get(root);
return 0;
}
ORZ