平衡树
Treap
模板
cpp
struct Node{
int l,r;//左右儿子
int key,val;//key为二叉搜索树的权值，val为堆的权值
int cnt,size;//cnt为当前为key的个数，size为子树大小
} t[N];
int root,idx;
void pushup(int p){
t[p].size=t[t[p].l].size+t[t[p].r].size+t[p].cnt;
}
int newNode(int key){
t[++idx].key=key;
t[idx].val=rand();
t[idx].cnt=t[idx].size=1;
return idx;
}
void build(){
newNode(-INF),newNode(INF);
root=1,t[1].r=2;//赋值哨兵，防止越界访问
pushup(root);
}
void zig(int &p){//右旋
int q=t[p].l;
t[p].l=t[q].r,t[q].r=p,p=q;
pushup(t[p].r);
pushup(p);
}
void zag(int &p){//左旋
int q=t[p].r;
t[p].r=t[q].l,t[q].l=p,p=q;
pushup(t[p].l);
pushup(p);
}
void insert(int &p,int key){
if(!p)p=newNode(key);
else if(t[p].key==key)t[p].cnt++;
else if(t[p].key>key){
insert(t[p].l,key);
if(t[t[p].l].val>t[p].val)zig(p);
}
else{
insert(t[p].r,key);
if(t[t[p].r].val>t[p].val)zag(p);
}
pushup(p);
}
void remove(int &p,int key){
if(!p)return;
if(t[p].key==key){
if(t[p].cnt>1)t[p].cnt--;
else if(t[p].l||t[p].r){
if(!t[p].r||t[t[p].l].val>t[t[p].r].val){
zig(p);//右旋之后的p为左儿子,p->t[p].r
remove(t[p].r,key);
}
else{
zag(p);
remove(t[p].l,key);
}
}
else p=0;
}
else if(t[p].key>key)remove(t[p].l,key);
else remove(t[p].r,key);
pushup(p);
}
int get_rank_by_key(int p,int key){
if(!p)return 1;
if(t[p].key==key)return t[t[p].l].size+1;
if(t[p].key>key)return get_rank_by_key(t[p].l,key);
return t[t[p].l].size+t[p].cnt+get_rank_by_key(t[p].r,key);
}
int get_key_by_rank(int p,int rank){
if(!p)return INF;
if(t[t[p].l].size>=rank)return get_key_by_rank(t[p].l,rank);
if(t[t[p].l].size+t[p].cnt>=rank)return t[p].key;
return get_key_by_rank(t[p].r,rank-t[t[p].l].size-t[p].cnt);
}
int get_prev(int p,int key){//找到严格小于key的最大值
if(!p)return -INF;
if(t[p].key>=key)return get_prev(t[p].l,key);
return max(t[p].key,get_prev(t[p].r,key));
}
int get_next(int p,int key){//找到严格大于key的最小值
if(!p)return INF;
if(t[p].key<=key)return get_next(t[p].r,key);
return min(t[p].key,get_next(t[p].l,key));
}
void solve(){
build();
int q;
cin>>q;
while(q--){
int op,x;
cin>>op>>x;
if(op==1)insert(root,x);
else if(op==2)remove(root,x);
else if(op==3)cout<<get_rank_by_key(root,x)-1<<"\n";//有一个负无穷，需要减一，下面同理
else if(op==4)cout<<get_key_by_rank(root,x+1)<<"\n";
else if(op==5)cout<<get_prev(root,x)<<"\n";
else cout<<get_next(root,x)<<"\n";
}
}pbds
cpp
#include<bits/extc++.h>
using namespace __gnu_pbds;
#define TR tree<PII,null_type,less<PII>,rb_tree_tag,tree_order_statistics_node_update>
void solve(){
TR tr;
int q;
cin>>q;
int cnt=0;
tr.insert({-INF,0});
tr.insert({INF,0});
while(q--){
int op,x,ans;
cin>>op>>x;
if(op==1)tr.insert({x,++cnt});//pbds平衡树无法记录个数，因此使用pair，第二维代表编号
else if(op==2)tr.erase(*tr.lower_bound({x,0}));
else if(op==3)cout<<tr.order_of_key(*tr.lower_bound({x,0}))<<"\n";
else if(op==4)cout<<tr.find_by_order(x)->first<<"\n";
else if(op==5)cout<<(--tr.lower_bound({x,0}))->first<<"\n";
else cout<<(tr.upper_bound({x,INF})->first)<<"\n";
}
}splay
FHQ-Treap
按值分裂
cpp
mt19937_64 rnd(114514);
struct FHQ{
int ls,rs,key,sz,val;
} fhq[N];s
int root,T1,T2,T3,idx;
int newNode(int val){
fhq[++idx]={0,0,(int)rnd(),1,val};
return idx;
}
void pushup(int u){
fhq[u].sz=fhq[fhq[u].ls].sz+fhq[fhq[u].rs].sz+1;
}
void split(int u,int val,int &x,int &y){
if(!u){
x=y=0;
return;
}
if(fhq[u].val>val){
y=u;
split(fhq[u].ls,val,x,fhq[u].ls);
}
else{
x=u;
split(fhq[u].rs,val,fhq[u].rs,y);
}
pushup(u);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(fhq[x].key>fhq[y].key){
fhq[x].rs=merge(fhq[x].rs,y);
pushup(x);
return x;
}
fhq[y].ls=merge(x,fhq[y].ls);
pushup(y);
return y;
}
void insert(int val){
split(root,val,T1,T2);
root=merge(merge(T1,newNode(val)),T2);
}
void erase(int x){
split(root,x,T1,T2);
split(T1,x-1,T1,T3);
T3=merge(fhq[T3].ls,fhq[T3].rs);
root=merge(merge(T1,T3),T2);
}
int find_rank(int x){
split(root,x-1,T1,T2);
int res=fhq[T1].sz+1;
root=merge(T1,T2);
return res;
}
int kth(int k){
int u=root;
while(u){
int tmp=fhq[fhq[u].ls].sz+1;
if(tmp==k)break;
if(k<tmp)u=fhq[u].ls;
else{
k-=tmp;
u=fhq[u].rs;
}
}
return fhq[u].val;
}
int find_prev(int u,int val){
if(u==0)return -INF;
if(fhq[u].val<val){
int res=find_prev(fhq[u].rs,val);
return res==-INF?fhq[u].val:res;
}
return find_prev(fhq[u].ls,val);
}
int find_next(int u,int val){
if(u==0)return INF;
if(fhq[u].val>val){
int res=find_next(fhq[u].ls,val);
return res==INF?fhq[u].val:res;
}
return find_next(fhq[u].rs,val);
}
void solve(){
int n;
cin>>n;
while(n--){
int op,x;
cin>>op>>x;
if(op==1)insert(x);
else if(op==2)erase(x);
else if(op==3)cout<<find_rank(x)<<"\n";
else if(op==4)cout<<kth(x)<<"\n";
else if(op==5)cout<<find_prev(root,x)<<"\n";
else cout<<find_next(root,x)<<"\n";
}
}按排名分裂
cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10,M=6010;
const int mod=1e9+7;
const int INF=1e18;
typedef pair<int,int> PII;
mt19937_64 rnd(114514);
struct FHQ{
int ls,rs,key,sz,val;
} fhq[N];
int root,T1,T2,T3,idx;
int newNode(int val){
fhq[++idx]={0,0,(int)rnd(),1,val};
return idx;
}
void pushup(int u){
fhq[u].sz=fhq[fhq[u].ls].sz+fhq[fhq[u].rs].sz+1;
}
void split(int u,int k,int &x,int &y){
if(!u){
x=y=0;
return;
}
int tmp=fhq[fhq[u].ls].sz+1;
if(k==tmp){
x=u;
y=fhq[u].rs;
fhq[u].rs=0;
}
else if(k<tmp){
y=u;
split(fhq[u].ls,k,x,fhq[u].ls);
}
else{
x=u;
split(fhq[u].rs,k-tmp,fhq[u].rs,y);
}
pushup(u);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(fhq[x].key>fhq[y].key){
fhq[x].rs=merge(fhq[x].rs,y);
pushup(x);
return x;
}
fhq[y].ls=merge(x,fhq[y].ls);
pushup(y);
return y;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
root=merge(root,newNode(i));
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
x%=fhq[root].sz;
split(root,x,T1,T2);
split(T2,1,T2,T3);
root=merge(T3,T1);
cout<<fhq[T2].val<<"\n";
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int T=1;
// cin>>T;
while(T--)solve();
return 0;
}文艺平衡树，按排名分裂
cpp
mt19937_64 rnd(114514);
struct FHQ{
int ls,rs,key,sz,val;
bool tag;
} fhq[N];
int root,T1,T2,T3,idx;
int newNode(int val){
fhq[++idx]={0,0,(int)rnd(),1,val};
return idx;
}
void pushup(int u){
fhq[u].sz=fhq[fhq[u].ls].sz+fhq[fhq[u].rs].sz+1;
}
void pushdown(int u){
if(fhq[u].tag){
swap(fhq[u].ls,fhq[u].rs);
if(fhq[u].ls)fhq[fhq[u].ls].tag^=1;
if(fhq[u].rs)fhq[fhq[u].rs].tag^=1;
fhq[u].tag=0;
}
}
void split(int u,int k,int &x,int &y){
if(!u){
x=y=0;
return;
}
pushdown(u);
int tmp=fhq[fhq[u].ls].sz+1;
if(k==tmp){
x=u;
y=fhq[u].rs;
fhq[u].rs=0;
}
else if(k<tmp){
y=u;
split(fhq[u].ls,k,x,fhq[u].ls);
}
else{
x=u;
split(fhq[u].rs,k-tmp,fhq[u].rs,y);
}
pushup(u);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(fhq[x].key>fhq[y].key){
pushdown(x);
fhq[x].rs=merge(fhq[x].rs,y);
pushup(x);
return x;
}
pushdown(y);
fhq[y].ls=merge(x,fhq[y].ls);
pushup(y);
return y;
}
void reverse(int l,int r){
split(root,l-1,T1,T2);
split(T2,r-l+1,T2,T3);
fhq[T2].tag^=1;
root=merge(merge(T1,T2),T3);
}
void dfs(int u){
if(!u)return;
pushdown(u);
dfs(fhq[u].ls);
cout<<fhq[u].val<<" ";
dfs(fhq[u].rs);
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
root=merge(root,newNode(i));
}
while(m--){
int l,r;
cin>>l>>r;
reverse(l,r);
}
dfs(root);
}P3224 [HNOI2012] 永无乡
题意：
n座桥，每座桥有个排名，初始有m条边，多次询问B x y在岛x和y之间修桥Q x k与x连通的第k小的岛
思路：
- 并查集维护连通性
- 平衡树本身不能合并，因此采取启发式合并，遍历小节点
P4402 [Cerc2007] robotic sort 机械排序(文艺平衡树)
题意：
每次找出第k小值的下标pos，然后翻转[i,pos]，问翻转前第k小值的下标
思路：
- 显然这是个排序操作，每次都能让第k小放到对应的位置
- fhq，点内维护一个mn值，然后每次可以查询与root相同的mn值的最小点，它的排名即当前第k小的排名
- 因为每次会让最小值向前，可以认为删除该最小值
- 所以每次查询最小值的排名，并反转即可