ZR 集训 Day4 – 平衡树及其应用

ooliver 发布于 1 天前 142 次阅读 OI

AI 摘要

只需掌握分裂与合并，FHQ Treap 就能轻松驾驭平衡树的所有操作！本文从普通平衡树出发，带你玩转文艺反转、机械排序与银河英雄传说的动态序列，最后解锁笛卡尔树的高效建堆——核心两招，应用无穷。

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;
}