#创作计划#浅谈启发式合并

亚洲卷王 AK IOI

2026-07-19 17:25:10

发布于：浙江

19阅读

0回复

0点赞

引入

假设我们有若干个集合，大小之和为 $n$ 。我们需要执行 $q$ 次操作，每次都是要合并其中两个集合，默认 $n,q$ 同阶。

暴力做法是显然的：枚举其中一个集合的所有元素，把它加入到另一个集合。

这样做复杂度显然是 $O(n^2)$ 的。

启发式合并

启发式合并的思路是比较简单的：在暴力做法的基础上，把小集合 $S$ 合并入大集合 $T$ 中。

这样做的复杂度看上去和暴力没什么区别，但是其实是 $O(n \log n)$ 的。证明如下：

考虑一个元素 $x$ 被枚举到的次数。假定 $x \in S$ ，把 $S$ 并入 $T$ 之后，新的集合 $T_0$ 大小肯定至少是 $S$ 的两倍，那么，如果我想让 $x$ 下一次继续并入大集合 $T_1$ 的时候， $T_1$ 肯定要满足： $\lvert T_1\rvert \geq \lvert T_0\rvert \geq 2\lvert S\rvert$ 。以此类推。也就是说， $\lvert T_m\rvert \geq 2^n\lvert S\rvert$ 。所以 $m \leq \log_2 n$ ，说明 $x$ 被枚举的次数是 $O(n\log n)$ 的，总复杂度是 $O(n \log n)$ 。

例题1

P3402 【模板】可持久化并查集

维护并查集，支持回退到第 $k$ 次操作。

可持久化就不说了，相信大家都会。

本题的并查集不能用路径压缩，因为路径压缩的复杂度是均摊 $\log$ 的，也就是总复杂度是 $O(n \log n)$ ，但不保证每次复杂度是 $O(\log n)$ 。所以如果查询一直回退到某一次复杂度比较大的操作，路径压缩就会炸。

所以，我们考虑启发式合并。考虑在合并并查集的时候，把小的合并到大的上面就可以了。

顺便提一嘴，并查集中的启发式合并又叫做按秩合并。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+15;
struct segtree{
    struct sgtree{
        ll ls,rs,val;
        sgtree(const ll &A=0,const ll &B=0,const ll &C=0):ls(A),rs(B),val(C){}
    };
    ll tot=0;
    ll rt[MAXN];
    sgtree sgt[MAXN<<5];
    #define ls(p) (sgt[p].ls)
    #define rs(p) (sgt[p].rs)
    inline ll bld(const ll &l,const ll &r,const vector<ll> &a){
        ll rt=++tot;
        if(l==r){
            sgt[rt]=sgtree(0,0,a[l]);
            return rt;
        }
        ll mid=l+r>>1;
        sgt[rt]=sgtree(bld(l,mid,a),bld(mid+1,r,a));
        return rt;
    }
    inline ll build(const ll &n,const vector<ll> &a){return bld(1,n,a);}
    inline ll upd1(const ll &q,const ll &l,const ll &r,const ll &p,const ll &c){
        ll rt=++tot;
        sgt[rt]=sgtree(ls(p),rs(p),sgt[p].val);
        if(l==r){
            sgt[rt].val+=c;
            return rt;
        }
        ll mid=l+r>>1;
        if(mid>=q) sgt[rt].ls=upd1(q,l,mid,ls(p),c);
        else sgt[rt].rs=upd1(q,mid+1,r,rs(p),c);
        return rt;
    }
    inline ll update1(const ll &q,const ll &n,const ll &opt,const ll &c){return upd1(q,1,n,rt[opt],c);}
    inline ll upd2(const ll &q,const ll &l,const ll &r,const ll &p,const ll &c){
        ll rt=++tot;
        sgt[rt]=sgtree(ls(p),rs(p),sgt[p].val);
        if(l==r){
            sgt[rt].val=c;
            return rt;
        }
        ll mid=l+r>>1;
        if(mid>=q) sgt[rt].ls=upd2(q,l,mid,ls(p),c);
        else sgt[rt].rs=upd2(q,mid+1,r,rs(p),c);
        return rt;
    }
    inline ll update2(const ll &q,const ll &n,const ll &opt,const ll &c){return upd2(q,1,n,rt[opt],c);}
    inline ll qry(const ll &q,const ll &l,const ll &r,const ll &p){
        if(l==r) return sgt[p].val;
        ll mid=l+r>>1;
        if(mid>=q) return qry(q,l,mid,ls(p));
        return qry(q,mid+1,r,rs(p));
    }
    inline ll query(const ll &q,const ll &n,const ll &opt){return qry(q,1,n,rt[opt]);}
};
ll n,m,op,u,v,k,opt;
segtree par,siz;
vector<ll> vpar,vsiz;
inline ll sfind(ll x){
    ll fa;
    while((fa=par.query(x,n,opt))!=x) x=fa;
    return x;
}
inline bool inset(const ll &x,const ll &y){return sfind(x)==sfind(y);}
inline void smerge(ll x,ll y){//启发式合并（按秩合并）
    if(inset(x,y)) return;
    x=sfind(x),y=sfind(y);
    ll sizx=siz.query(x,n,opt),sizy=siz.query(y,n,opt);
    if(sizx<sizy){
        swap(x,y);
        swap(sizx,sizy);
    }
    par.rt[opt]=par.update2(y,n,opt,x);
    siz.rt[opt]=siz.update1(x,n,opt,sizy);
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    vpar.resize(n+1),vsiz.resize(n+1);
    for(ll i=1;i<=n;i++){
        vpar[i]=i;
        vsiz[i]=1;
    }
    par.rt[0]=par.build(n,vpar);
    siz.rt[0]=siz.build(n,vsiz);
    for(opt=1;opt<=m;opt++){
        par.rt[opt]=par.rt[opt-1];
        siz.rt[opt]=siz.rt[opt-1];
        cin>>op;
        if(op==1){
            cin>>u>>v;
            smerge(u,v);
        }
        else if(op==2){
            cin>>k;
            par.rt[opt]=par.rt[k];
            siz.rt[opt]=siz.rt[k];
        }
        else{
            cin>>u>>v;
            cout<<inset(u,v)<<'\n';
        }
    }
    return 0;
}

例题2

P3201 [HNOI2009] 梦幻布丁

给定长度为 $n$ 的颜色序列， $m$ 次操作。

操作一：把颜色 $x$ 都变成 $y$ 。

操作二：查询有多少颜色段。

我们可以预先求出答案，在每次合并的时候更新答案。

考虑使用 set[N] 表示每一种颜色的位置。合并的时候把小 set 合并进大 set 。对于小 set 中的位置 $p$ ，如果 $a_{p-1}=y$ ，则这两段颜色会合并为一段，答案减去 $1$ ；如果 $a_{p+1}=y$ ，也要减去 $1$ 。

不过有一个问题，启发式合并的交换可能会把 $y$ 变成 $x$ ，所以我们定义 $c_i$ 表示颜色 $i$ 的真实颜色，然后把启发式合并的交换改成 $c_x$ 与 $c_y$ 的交换。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e6+16;
ll n,m,op,x,y,ans;
ll a[MAXN],id[MAXN];
set<ll> sets[MAXN];
void merge(const ll &x,const ll &y){
    if(x==y) return;
    if(sets[id[x]].size()>sets[id[y]].size()) swap(id[x],id[y]);
    for(auto &i:sets[id[x]]){
        if(a[i-1]==id[y]) ans--;
        if(a[i+1]==id[y]) ans--;
    }
    for(auto &i:sets[id[x]]) a[i]=id[y];
    for(auto &i:sets[id[x]]) sets[id[y]].insert(i);
    sets[id[x]].clear();
    return;
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        id[a[i]]=a[i];
        sets[a[i]].insert(i);
    }
    for(ll i=1;i<=n;i++) ans+=a[i]!=a[i-1];
    while(m--){
        cin>>op;
        if(op==1){
            cin>>x>>y;
            merge(x,y);
        }
        else cout<<ans<<'\n';
    }
    return 0;
}

树上启发式合并

树上启发式合并的思路是，对于节点 $u$ ，先计算它的轻儿子 $v$ 自己的答案，计算完立刻清空计算用的数组，再计算重儿子 $h$ 的答案，不清空，然后加上 $u$ 节点的贡献，最后再次遍历轻儿子 $v$ ，把每一个节点的贡献加进来，最终计算出 $u$ 的答案。当然，如果 $u$ 是 $u$ 的父亲的轻儿子，还要把自己清空。

假如计算一个节点的贡献是 $O(1)$ ，那么总时间复杂度是 $O(n \log n)$ ，证明如下：

考虑每一个轻儿子 $v$ 会被遍历多少次。 $v$ 被遍历一次，对应着一条从 $1$ 到 $v$ 路径上的轻边，所以遍历次数为 $1$ 到 $v$ 路径上有多少条轻边。

假设 $u \rightarrow v$ 是轻边，那么 $size(v) \leq \frac{size(u)}{2}$ 。

如果 $size(v)>\frac{size(u)}{2}$ ，那么 $u\rightarrow v$ 就是重边，矛盾。

所以，每经过一条轻边，子树大小至少缩小一半。因此，从 $1$ 到 $v$ 的轻边数量不超过 $\log_2 n$ 。

所以，总时间复杂度是 $O(n \log n)$ 。

通过证明可以知道，树上启发式合并基本跑不满。

例题1

CF600E Lomsat gelral

给定根为 $1$ 的有根树，每个点有颜色，对于所有节点，求出其子树内众数的颜色编号之和。

考虑加入一个新节点 $v$ 对 $u$ 子树的答案的贡献。定义 $cnt_i$ 表示颜色 $i$ 的出现次数， $maxx$ 表示出现次数的最大值， $sum$ 表示众数的颜色编号之和。

加入 $v$ 后，设 $c$ 表示 $v$ 的颜色，如果 $cnt_c>maxx$ ，那么更新 $maxx$ ，重置 $sum=c$ ；如果 $cnt_c=maxx$ ，那么累加 $sum := sum+c$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
//dfs1求重儿子，dfs2加贡献，dfs3清空，dfs4树上dsu
#define ll long long
const ll MAXN=1e5+15;
struct graph{
    ll nxt,to;
    graph(const ll &A=0,const ll &B=0):nxt(A),to(B){}
};
ll n,u,v,maxx,sum,tot=1;
ll hd[MAXN],c[MAXN],ans[MAXN],cnt[MAXN],siz[MAXN],hson[MAXN];
graph edge[MAXN<<1];
void add(const ll &u,const ll &v){
    edge[++tot]=graph(hd[u],v);
    hd[u]=tot;
    edge[++tot]=graph(hd[v],u);
    hd[v]=tot;
    return;
}
void dfs1(const ll &u,const ll &fath){
    ll v;
    siz[u]=1;
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath){
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[hson[u]]) hson[u]=v;
        }
    }
    return;
}
void dfs2(const ll &u,const ll &fath){
    ll v;
    cnt[c[u]]++;
    if(cnt[c[u]]>maxx){
        maxx=cnt[c[u]];
        sum=c[u];
    }
    else if(cnt[c[u]]==maxx) sum+=c[u];
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath) dfs2(v,u);
    }
    return;
}
void dfs3(const ll &u,const ll &fath){
    ll v;
    cnt[c[u]]--;
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath) dfs3(v,u);
    }
    return;
}
void dfs4(const ll &u,const ll &fath,const bool &hs){
    ll v;
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath&&v!=hson[u]) dfs4(v,u,false);
    }
    if(hson[u]) dfs4(hson[u],u,true);
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath&&v!=hson[u]) dfs2(v,u);
    }
    cnt[c[u]]++;
    if(cnt[c[u]]>maxx){
        maxx=cnt[c[u]];
        sum=c[u];
    }
    else if(cnt[c[u]]==maxx) sum+=c[u];
    ans[u]=sum;
    if(!hs){
        maxx=sum=0;
        dfs3(u,fath);
    }
    return;
}
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>c[i];
    for(ll i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
    }
    dfs1(1,0);
    dfs4(1,0,false);
    for(ll i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}

例题2

CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

给定一颗根为 $1$ 的有根树，每条边有一个小写字母（从 $a$ 到 $v$ ）。

如果一条简单路径经过的所有边的字母可以排列出回文串，那么它就是特殊路径。

对于所有节点 $u$ ，询问 $u$ 的子树中，最长的特殊路径长度。

我们考虑什么样的路径是特殊的。显然，经过的字母数量最多只能有一个是奇数。因此，我们只关心字母出现次数的奇偶性。

由于字母只有 $22$ 种，考虑状态压缩进一个整数里。 $d_i$ 表示从 $1$ 到 $i$ 路径上所有字母的状压后的值。如果 $\operatorname{popcount}(d_u \oplus d_v) \leq 1$ ，那么 $u \rightarrow v$ 的路径就是特殊的。

定义 $dep_u$ 表示 $u$ 的深度， $maxd_i$ 表示 $d_v=i$ 中 $dep_{v}$ 的最大值， $ans_u$ 表示 $u$ 点的答案。对于 $u$ 的轻儿子 $v$ ，我们遍历 $v$ 的子树中的点 $v'$ ，令 $D=d_{v'}$ ，更新 $ans_u=\max(maxd_{D}+dep_{v'}-2dep_u,maxd_{D \oplus 2^i}+dep_{v'}-2dep_u,ans_v)$ 。

更新之后，再将 $v$ 的子树所有节点的贡献加进去。

为什么这样是对的？因为在更新的过程中，还没有加入过 $v$ 的子树的节点，所以更新时，不会遇到 $v' \rightarrow u \rightarrow v'$ 这种非法路径。

小细节， $maxd$ 清空的时候要设为负无穷，而不是 $0$ 。

时间复杂度： $O(nV \log n)$ ，本题 $V=22$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5e5+55;
struct graph{
    ll nxt,to,w;
    graph(const ll &A=0,const ll &B=0,const ll &C=0):nxt(A),to(B),w(C){}
};
ll n,u,v,tot=1;
char ch;
ll hd[MAXN],d[MAXN],dep[MAXN],maxd[1<<22],ans[MAXN],siz[MAXN],hson[MAXN];
graph edge[MAXN<<1];
void add(const ll &u,const ll &v,const ll &w){
    edge[++tot]=graph(hd[u],v,w);
    hd[u]=tot;
    edge[++tot]=graph(hd[v],u,w);
    hd[v]=tot;
    return;
}
void dfs1(const ll &u,const ll &fath){
    ll v,w;
    dep[u]=dep[fath]+1;
    siz[u]=1;
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to,w=edge[i].w;
        if(v!=fath){
		    d[v]=d[u]^w;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[hson[u]]) hson[u]=v;
        }
    }
    return;
}
void dfs2(const ll &u,const ll &fath,const ll &rt){
    ll v;
    ans[rt]=max(maxd[d[u]]+dep[u]-2*dep[rt],ans[rt]);
    for(ll i=0;i<22;i++) ans[rt]=max(maxd[d[u]^(1<<i)]+dep[u]-2*dep[rt],ans[rt]);
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath) dfs2(v,u,rt);
    }
    return;
}
void dfs3(const ll &u,const ll &fath){
    ll v;
    maxd[d[u]]=max(dep[u],maxd[d[u]]);
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath) dfs3(v,u);
    }
    return;
}
void dfs4(const ll &u,const ll &fath){
    ll v;
    maxd[d[u]]=-1e9;
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath) dfs4(v,u);
    }
    return;
}
void dfs5(const ll &u,const ll &fath,const bool &hs){
    ll v;
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath&&v!=hson[u]) dfs5(v,u,false);
    }
    if(hson[u]){
        dfs5(hson[u],u,true);
        ans[u]=max({ans[hson[u]],maxd[d[u]]-dep[u],ans[u]});
        for(ll i=0;i<22;i++) ans[u]=max(maxd[d[u]^(1<<i)]-dep[u],ans[u]);
    }
    maxd[d[u]]=max(dep[u],maxd[d[u]]);
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath&&v!=hson[u]){
            ans[u]=max(ans[v],ans[u]);
            dfs2(v,u,u);
            dfs3(v,u);
        }
    }
    if(!hs) dfs4(u,fath);
    return;
}
int main(){
	memset(maxd,0xcf,sizeof(maxd));
    cin>>n;
    for(ll i=2;i<=n;i++){
        cin>>u>>ch;
        add(u,i,1<<(ch-'a'));
    }
    dfs1(1,0);
    dfs5(1,0,false);
    for(ll i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}

例题3

P5290 [十二省联考 2019] 春节十二响

给定一颗的有根树，有点权，将其划分为若干个点集合，要求每个集合内的点不存在祖先关系，最小化所有集合内最大值之和。

先考虑特殊性质，如果树是一条链，那么 $1$ 号点将链划分为两段，我们肯定是让第一段的最大值和第二段最大值在一起，第一段次大值和第二段次大值在一起……也就是对于两段分别开一个大根堆，每次取堆顶划成一个集合。

这提示我们，设 $heap_u$ 表示 $u$ 子树内，我们划分出的每一个集合的最大值所构成的大根堆。对于 $u$ 的儿子 $v$ ，我们把 $heap_v$ 与 $heap_u$ 合并，最后再单独把 $M_u$ 单独扔到堆里。

此时使用启发式合并就是 $O(n \log n)$ 的。为什么不是 $O(n \log^2 n)$ 呢？因为本题的 $heap_v$ 并没有真正并入 $heap_u$ ，只是取了一个 $\max$ ，所以每个点只会被合并 $1$ 次，而不是 $\log_2 n$ 次。

注意，本题与P3201 [HNOI2009] 梦幻布丁类似，由于有启发式合并的交换操作，所以要记录每个节点真正的编号。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25;
struct graph{
    ll nxt,to;
    graph(const ll &A=0,const ll &B=0):nxt(A),to(B){}
};
ll n,u,ans,tot=1;
ll hd[MAXN],id[MAXN],m[MAXN];
priority_queue<ll> pq[MAXN];
graph edge[MAXN];
void add(const ll &u,const ll &v){
    edge[++tot]=graph(hd[u],v);
    hd[u]=tot;
    return;
}
void dfs(const ll &u){
    ll v,x,y;
    vector<ll> vec;
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        dfs(v);
        if(pq[id[u]].size()<pq[id[v]].size()) swap(id[u],id[v]);
        while(!pq[id[v]].empty()){
            x=pq[id[u]].top(),y=pq[id[v]].top();
            vec.push_back(max(x,y));
            pq[id[u]].pop();
            pq[id[v]].pop();
        }
        for(auto &j:vec) pq[id[u]].push(j);
        vec.clear();
    }
    pq[id[u]].push(m[u]);
    return;
}
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>m[i];
        id[i]=i;
    }
    for(ll i=2;i<=n;i++){
        cin>>u;
        add(u,i);
    }
    dfs(1);
    while(!pq[id[1]].empty()){
        ans+=pq[id[1]].top();
        pq[id[1]].pop();
    }
    cout<<ans;
    return 0;
}

例题4

CF1709E XOR Tree

给定一棵树，带点权，你可以进行若干次如下操作：把一个点的点权改成一个任意正整数。求最少次操作，使得不存在异或和为 $0$ 的简单路径。

由于我们修改点权是任意数，所以可以当作是把这个点以及连的边都删掉。

设 $d_u$ 表示从 $1$ 到 $u$ 的异或和，显然 $u \rightarrow v$ 的异或和是 $d_u \oplus d_v \oplus a_{\operatorname{LCA}(u,v)}$ 。

考虑自底向上贪心。枚举 $x$ ，判断是否存在 $u,v$ 使得 $\operatorname{LCA}(u,v)=x$ 并且 $d_u \oplus d_v=a_x$ ，如果有，那就删除 $x$ 。

设 $S_x$ 表示 $x$ 子树内未被删除的节点的 $d$ 值。先把 $d_x$ 加入 $S_x$ ，接着我们枚举 $x$ 的子树 $u$ ，遍历 $i \in S_u$ ，判断 $i \oplus a_x$ 是否属于 $S_x$ 。如果是，说明 $x$ 需要删除，清空 $S_x$ 并不再枚举。如果最后不需要删除，就把 $S_u$ 合并到 $S_x$ 中。这个过程使用启发式合并，可以做到 $O(n \log^2 n)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25;
struct graph{
    ll nxt,to;
    graph(const ll &A=0,const ll &B=0):nxt(A),to(B){}
};
ll n,u,v,ans,tot=1;
ll hd[MAXN],a[MAXN],d[MAXN],id[MAXN];
graph edge[MAXN<<1];
set<ll> s[MAXN];
void add(const ll &u,const ll &v){
    edge[++tot]=graph(hd[u],v);
    hd[u]=tot;
    edge[++tot]=graph(hd[v],u);
    hd[v]=tot;
    return;
}
void dfs1(const ll &u,const ll &fath){
    ll v;
    d[u]=a[u]^d[fath];
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath) dfs1(v,u);
    }
    return;
}
void dfs2(const ll &u,const ll &fath){
    ll v;
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath) dfs2(v,u);
    }
    s[id[u]].insert(d[u]);
    for(ll i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath){
            if(s[id[u]].size()<s[id[v]].size()) swap(id[u],id[v]);
            for(auto &j:s[id[v]]){
                if(s[id[u]].count(j^a[u])){
                    ans++;
                    s[id[u]].clear();
                    return;
                }
            }
            for(auto &j:s[id[v]]) s[id[u]].insert(j);
            s[id[v]].clear();
        }
    }
    return;
}
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        id[i]=i;
    }
    for(ll i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
    }
    dfs1(1,0);
    dfs2(1,0);
    cout<<ans;
    return 0;
}