ZR 集训 Day4 – 平衡树及其应用
P6136 【模板】普通平衡树（数据加强版）（P3369 【模板】普通平衡树）
这俩就改改输入的区别，就按加强版来讲了。
这里使用的是 FHQ Treap，因为它非常简洁易懂，只需要核心掌握两个操作：分裂和合并。
分裂
分裂函数需要四个参数 $u,key,x,y$，意思是将以 $u$ 为根的 Treap 按 $key$ 分裂成以 $x$，$y$ 为根的两个子树。
具体实现：若当前子树的根 $u$ 的权值小于或等于 $key$，那就把 $x$ 设为 $u$，把 $u$ 的左儿子分给 $x$，并递归 $u$ 的右儿子，将右儿子中小于或等于 $key$ 的分到 $x$ 的右儿子，其余分给 $y$；反之亦然。
C++
void pushup(int u){
sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;
}
void split(int u,int key,int &x,int &y){
if(!u){
x=y=0;
return;
}
if(val[u]<=key) x=u,split(ch[u][1],key,ch[u][1],y);
else y=u,split(ch[u][0],key,x,ch[u][0]);
pushup(u);
}合并
合并 $x$，$y$ 两颗 Treap 的前提是 $x$ 内的全部权值都要小于 $y$ 内的任意一个权值。
比较两颗 Treap 的随机优先级，将优先级低的合并到优先级高的上。
若 $x$ 优先级更高，则将 $y$ 与 $x$ 的右儿子递归合并；反之亦然。
C++
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;
}
}添加
添加一个权值为 $v$ 的点。
先根据权值 $v$ 建一个点 $u$。
定义两颗子树，将原 Treap 按照 $v$ 分裂成两部分，再加上新建节点 $u$ 一起合并即可。
C++
int newd(int v){
val[++idx]=v,sz[idx]=1,rnd[idx]=rand();
ch[idx][0]=ch[idx][1]=0;
return idx;
}
void insert(int v){
int x,y,u=newd(v);
split(rt,v,x,y);
rt=merge(merge(x,u),y);
}删除
删除一个权值为 $v$ 的点。
先按照 $v-1$ 把原 Treap 分裂成两个子树 $x$ 和 $y$，再按照 $v$ 把 $y$ 分裂成 $y$ 和 $z$。
此时 $x$ 内点权全部小于 $v$，$y$ 内点权全部等于 $v$，$z$ 内点权全部大于 $v$。
此时直接合并 $y$ 的左右儿子，相当于不管 $y$ 这个根了，最后再把 $x$，$y$，$z$ 合并起来，就完成了。
C++
void del(int v){
int x,y,z;
split(rt,v-1,x,y);
split(y,v,y,z);
if(!y){
rt=merge(x,z);
return;
}
y=merge(ch[y][0],ch[y][1]);
rt=merge(x,merge(y,z));
}排名
询问权值 $v$ 的排名。
将原 Treap 按 $v-1$ 分裂成 $x$，$y$ 两部分，$x$ 部分的子树大小就是小于 $v$ 的个数，加一就是 $v$ 的排名。
C++
int rk(int v){
int x,y,res;
split(rt,v-1,x,y);
res=sz[x]+1;
rt=merge(x,y);
return res;
}第 K 大
直接在 Treap 上做类似二分的操作即可。
C++
int kth(int k){
int u=rt;
while(1){
if(k<=sz[ch[u][0]]) u=ch[u][0];
else if(k==sz[ch[u][0]]+1) return val[u];
else k-=sz[ch[u][0]]+1,u=ch[u][1];
}
}前驱、后继
根据排名找到对应点即可，可使用前面定义的函数得到。
C++
int pre(int v){
return kth(rk(v)-1);
}
int suc(int v){
return kth(rk(v+1));
}总代码
C++
#include<bits/stdc++.h>
using namespace std;
const int N=2e6;
int n,m,rt,idx,last,ans;
int ch[N][2],val[N],sz[N],rnd[N];
void pushup(int u){
sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;
}
int newd(int v){
val[++idx]=v,sz[idx]=1,rnd[idx]=rand();
ch[idx][0]=ch[idx][1]=0;
return idx;
}
void split(int u,int key,int &x,int &y){
if(!u){
x=y=0;
return;
}
if(val[u]<=key) x=u,split(ch[u][1],key,ch[u][1],y);
else y=u,split(ch[u][0],key,x,ch[u][0]);
pushup(u);
}
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;
}
}
void insert(int v){
int x,y,u=newd(v);
split(rt,v,x,y);
rt=merge(merge(x,u),y);
}
void del(int v){
int x,y,z;
split(rt,v-1,x,y);
split(y,v,y,z);
if(!y){
rt=merge(x,z);
return;
}
y=merge(ch[y][0],ch[y][1]);
rt=merge(x,merge(y,z));
}
int rk(int v){
int x,y,res;
split(rt,v-1,x,y);
res=sz[x]+1;
rt=merge(x,y);
return res;
}
int kth(int k){
int u=rt;
while(1){
if(k<=sz[ch[u][0]]) u=ch[u][0];
else if(k==sz[ch[u][0]]+1) return val[u];
else k-=sz[ch[u][0]]+1,u=ch[u][1];
}
}
int pre(int v){
return kth(rk(v)-1);
}
int suc(int v){
return kth(rk(v+1));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
srand(time(0));
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
insert(x);
}
while(m--){
int op,x;
cin>>op>>x;
x^=last;
if(op==1) insert(x);
else if(op==2) del(x);
else if(op==3) last=rk(x);
else if(op==4) last=kth(x);
else if(op==5) last=pre(x);
else last=suc(x);
if(op>=3) ans^=last;
}
cout<<ans<<"\n";
return 0;
}P3391 【模板】文艺平衡树
与模板平衡树不同的是，文艺平衡树中每个点维护的是其在序列中的位置。当它在序列中位置发生变化是，二叉树的结构也随之变化，但二叉树的中序遍历始终是序列。
考虑当序列反转时，我们将反转的部分序列分割出来，相当于这个子树每个左右儿子都要左右调换，但是直接遍历相当于暴力，我们可以利用懒标记，给子树的根打上懒标记，当下次需要遍历子树时再把懒标记下传，维持树的结构。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,rt,idx;
int son[N][2],vis[N],siz[N],rnd[N],lazy[N];
void pushup(int u){
siz[u]=siz[son[u][0]]+siz[son[u][1]]+1;
}
void pushdown(int u){
if(lazy[u]){
swap(son[u][0],son[u][1]);
lazy[son[u][0]]=!lazy[son[u][0]];
lazy[son[u][1]]=!lazy[son[u][1]];
lazy[u]=0;
}
}
int newd(int v){
vis[++idx]=v,siz[idx]=1,rnd[idx]=rand();
son[idx][0]=son[idx][1]=0;
return idx;
}
void split(int u,int key,int &x,int &y){
if(!u){
x=y=0;
return;
}
pushdown(u);
if(siz[son[u][0]]+1<=key) x=u,split(son[u][1],key-siz[son[u][0]]-1,son[u][1],y);
else y=u,split(son[u][0],key,x,son[u][0]);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(rnd[x]<rnd[y]){
pushdown(x);
son[x][1]=merge(son[x][1],y);
pushup(x);
return x;
}
else{
pushdown(y);
son[y][0]=merge(x,son[y][0]);
pushup(y);
return y;
}
}
void insert(int v){
int x,y,u=newd(v);
split(rt,v,x,y);
rt=merge(merge(x,u),y);
}
void solve(int l,int r){
int x,y,z;
split(rt,l-1,x,y);
split(y,r-l+1,y,z);
lazy[y]^=1;
merge(merge(x,y),z);
}
void dfs(int u){
pushdown(u);
if(son[u][0]) dfs(son[u][0]);
cout<<vis[u]<<" ";
if(son[u][1]) dfs(son[u][1]);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
srand(time(0));
cin>>n>>m;
for(int i=1;i<=n;i++) insert(i);
while(m--){
int l,r;
cin>>l>>r;
solve(l,r);
}
dfs(rt);
return 0;
}P4402 [CERC2007] robotic sort 机械排序
观察题目，当我们每次进行“找到编号最小的物品的位置 $P_1$，将区间 $[1,P_1]$ 反转，再找到编号第二小的物品的位置 $P_2$，将区间 $[2,P_2]$ 反转......”操作时，较小的物品都会被反转至开头，并且在后续的反转后不会再被操作，所以我们可以视为每次找到当前序列最小值、进行反转操作、并删除它。
对于反转而言，不难想到和上题一样打懒标记。但我们要动态求最小并保证序列有序，这和平衡树模板稍有不同，这是就要介绍一个高级科技：笛卡尔树注。笛卡尔树的每个点有两个信息，保证在中序遍历时一个信息与序列一样、同时保证另一个信息在树上形成小根堆。在这我们保证节点编号有序，并使物品大小形成小根堆。这时每次只需求出根左子树的大小并加 $1$，同时还要加上之前被放在序列开头、被我们忽略的前 $i-1$ 个点。输出答案后对左子树打上懒标记，并把左右子树合并即可。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6;
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
int n,m,rt,idx,top;
int ch[N][2],sz[N],tag[N],st[N],rnd[N];
void pushup(int u){
sz[u]=sz[lc(u)]+sz[rc(u)]+1;
}
void pushdown(int u){
if(tag[u]){
swap(lc(u),rc(u));
tag[lc(u)]=!tag[lc(u)];
tag[rc(u)]=!tag[rc(u)];
tag[u]=0;
}
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(rnd[x]<rnd[y]){
pushdown(x);
rc(x)=merge(rc(x),y);
pushup(x);
return x;
}
else{
pushdown(x);
lc(y)=merge(x,lc(y));
pushup(y);
return y;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1,x;i<=n;i++){
int res=0;
cin>>x;
sz[i]=1,rnd[i]=1*x*(n+1)+i;
while(top&&rnd[st[top]]>rnd[i]){
res=st[top--];
pushup(res);
}
ch[i][0]=res;
if(top) ch[st[top]][1]=i;
st[++top]=i;
}
while(top) pushup(st[top--]);
rt=st[1];
for(int i=1;i<=n;i++){
pushdown(rt);
cout<<sz[lc(rt)]+i<<" ";
tag[lc(rt)]^=1;
rt=merge(lc(rt),rc(rt));
}
return 0;
}注：P5854 【模板】笛卡尔树
笛卡尔树是一种二叉树，每一个节点由一个键值二元组 $(k,w)$ 构成，要求 $k$ 满足二叉搜索树的性质，而 $w$ 满足堆的性质。——OI Wiki
我们用一个栈维护笛卡尔树的右链（即一直走右儿子的链，如图应为链 $1-5$；不难发现右链对应的 $w$ 应该是递增的），从左往右（按 $k$ 升序，一般 $k$ 为元素下标）添加元素。若栈顶的 $w$ 大于当前元素的 $w$，就将其出栈，并将最后一个出栈的元素设为当前元素的左儿子；如果栈不为空，就将当前元素设为栈顶的右儿子。这样进行一次后，栈底元素就应该是树根。因为每个元素至多入栈出栈一次，所以时间复杂度为线性。
模板题的代码：
C++
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n;
long long ansl,ansr;
int a[N],ch[N][2];
stack<int> s;
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int res=0;
scanf("%d",&a[i]);
while(s.size()&&a[s.top()]>a[i]) res=s.top(),s.pop();
ch[i][0]=res;
if(s.size()) ch[s.top()][1]=i;
s.push(i);
}
for(int i=1;i<=n;i++) ansl^=1ll*i*(ch[i][0]+1ll),ansr^=1ll*i*(ch[i][1]+1ll);
printf("%lld %lld",ansl,ansr);
return 0;
}P4847 银河英雄传说V2
看到序列合并、分裂等操作，立马可以想到 FHQ Treap。我们用每个 Treap 的根代表这个 Treap，每当 Treap 的结构发生改变时，就更新每个点的父亲和两个儿子。对于寻找一个点所在 Treap 的根，因为 Treap 的深度是接近 $\log$ 级别的，所以直接暴力向上找父亲节点就行。对于 split 操作，同样是根据子树的 $size$ 选择子节点来递归。由于要求序列元素之和，所以我们再定义一个 $sum$ 表示子树元素之和，通过两次分裂隔离出询问区间，输出其 $sum$ 即可。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int n,m,rt,idx;
int ch[N][2],val[N],sum[N],sz[N],rnd[N],fa[N];
void pushup(int u){
sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;
sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+val[u];
fa[ch[u][0]]=fa[ch[u][1]]=u;
}
void split(int u,int key,int &x,int &y,int fx,int fy){
if(!u){
x=y=0;
return;
}
if(sz[ch[u][0]]<key) x=u,split(ch[u][1],key-sz[ch[u][0]]-1,ch[u][1],y,u,fy);
else y=u,split(ch[u][0],key,x,ch[u][0],fx,u);
if(x) fa[x]=fx;
if(y) fa[y]=fy;
pushup(u);
}
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);
fa[ch[x][1]]=x;
pushup(x);
return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
fa[ch[y][0]]=y;
pushup(y);
return y;
}
}
int getrt(int u){
while(fa[u]) u=fa[u];
return u;
}
int sml(int u){
int res=sz[ch[u][0]];
while(fa[u]){
if(ch[fa[u]][1]==u) res+=sz[ch[fa[u]][0]]+1;
u=fa[u];
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
srand(time(0));
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>val[i];
sum[i]=val[i],sz[i]=1,rnd[i]=rand();
}
while(m--){
char op;
int x,y;
cin>>op;
if(op=='M'){
cin>>x>>y;
int rx=getrt(x),ry=getrt(y);
if(rx!=ry) merge(ry,rx);
}
else if(op=='D'){
cin>>x;
int v=sml(x),rx,ry;
split(getrt(x),v,rx,ry,0,0);
}
else{
cin>>x>>y;
int rx=getrt(x),ry=getrt(y);
if(rx!=ry){
cout<<"-1\n";
continue;
}
int a,b,c;
int sx=sml(x),sy=sml(y);
if(sx>sy) swap(sx,sy),swap(x,y);
split(rx,sy+1,b,c,0,0);
split(b,sx,a,b,0,0);
cout<<sum[b]<<"\n";
merge(merge(a,b),c);
}
}
return 0;
}P3380 【模板】树套树
线段树套 FHQ 的模板，在线段树的每个区间建一个 FHQ 即可。
此题超级卡常，多交几遍就好了。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
#define lc p<<1
#define rc p<<1|1
const int N=2e5+5,inf=2147483647;
int n,m,tot;
int a[N],ch[N*80][2],val[N*80],sz[N*80],rnd[N*80];
struct fhq{
int rt;
int newnode(int v){
++tot;
val[tot]=v,sz[tot]=1,rnd[tot]=rand();
ch[tot][0]=ch[tot][1]=0;
return tot;
}
void pushup(int u){sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1;}
void split(int u,int key,int &x,int &y){
if(!u){x=y=0;return;}
if(val[u]<=key) x=u,split(ch[u][1],key,ch[u][1],y);
else y=u,split(ch[u][0],key,x,ch[u][0]);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(rnd[x]<rnd[y]) return ch[x][1]=merge(ch[x][1],y),pushup(x),x;
else return ch[y][0]=merge(x,ch[y][0]),pushup(y),y;
}
void insert(int v){
int x,y,u=newnode(v);
split(rt,v,x,y);
rt=merge(merge(x,u),y);
}
void del(int v){
int x,y,z;
split(rt,v-1,x,y);
split(y,v,y,z);
if(!y){rt=merge(x,z);return;}
y=merge(ch[y][0],ch[y][1]);
rt=merge(x,merge(y,z));
}
int rk(int v){
int x,y,res;
split(rt,v-1,x,y);
res=sz[x];
rt=merge(x,y);
return res;
}
int pre(int v){
int x,y,res;
split(rt,v-1,x,y);
if(!x){rt=merge(x,y);return -inf;}
int u=x;
while(ch[u][1]) u=ch[u][1];
res=val[u];
rt=merge(x,y);
return res;
}
int suc(int v){
int x,y,res;
split(rt,v,x,y);
if(!y){rt=merge(x,y);return inf;}
int u=y;
while(ch[u][0]) u=ch[u][0];
res=val[u];
rt=merge(x,y);
return res;
}
}tr[N*4];
inline int read(){
int x=0,f=1;char ch=getchar_unlocked();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar_unlocked();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar_unlocked();}
return x*f;
}
inline void write(int x){
if(x<0) putchar_unlocked('-'),x=-x;
if(x>9) write(x/10);
putchar_unlocked(x%10+'0');
}
void build(int p,int l,int r){
for(int i=l;i<=r;i++) tr[p].insert(a[i]);
if(l==r) return;
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void change(int p,int l,int r,int pos,int k){
tr[p].del(a[pos]);
tr[p].insert(k);
if(l==r){a[pos]=k;return;}
int mid=l+r>>1;
if(pos<=mid) change(lc,l,mid,pos,k);
else change(rc,mid+1,r,pos,k);
}
int qrk(int p,int l,int r,int ql,int qr,int k){
if(ql<=l&&r<=qr) return tr[p].rk(k);
int mid=l+r>>1,res=0;
if(ql<=mid) res+=qrk(lc,l,mid,ql,qr,k);
if(qr>mid) res+=qrk(rc,mid+1,r,ql,qr,k);
return res;
}
int qkth(int l,int r,int k){
int L=0,R=1e8,ans;
while(L<=R){
int mid=L+R>>1;
if(qrk(1,1,n,l,r,mid)+1<=k) ans=mid,L=mid+1;
else R=mid-1;
}
return ans;
}
int qpre(int p,int l,int r,int ql,int qr,int k){
if(ql<=l&&r<=qr) return tr[p].pre(k);
int mid=l+r>>1,res=-inf;
if(ql<=mid) res=max(res,qpre(lc,l,mid,ql,qr,k));
if(qr>mid) res=max(res,qpre(rc,mid+1,r,ql,qr,k));
return res;
}
int qsuc(int p,int l,int r,int ql,int qr,int k){
if(ql<=l&&r<=qr) return tr[p].suc(k);
int mid=l+r>>1,res=inf;
if(ql<=mid) res=min(res,qsuc(lc,l,mid,ql,qr,k));
if(qr>mid) res=min(res,qsuc(rc,mid+1,r,ql,qr,k));
return res;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
while(m--){
int op,l,r,k,pos;
op=read();
if(op==1){
l=read(),r=read(),k=read();
write(qrk(1,1,n,l,r,k)+1),putchar_unlocked('\n');
}
else if(op==2){
l=read(),r=read(),k=read();
write(qkth(l,r,k)),putchar_unlocked('\n');
}
else if(op==3){
pos=read(),k=read();
change(1,1,n,pos,k);
}
else if(op==4){
l=read(),r=read(),k=read();
write(qpre(1,1,n,l,r,k)),putchar_unlocked('\n');
}
else{
l=read(),r=read(),k=read();
write(qsuc(1,1,n,l,r,k)),putchar_unlocked('\n');
}
}
return 0;
}
Comments NOTHING