QOJ# 9904. 最小生成树

题意

给定一个有 nn 个节点的无向完全图、序列 a3∼a2n−1a_3\sim a_{2n-1}，边 (i,j)(i,j) 的边权为 ai+ja_{i+j}，求该图最小生成树的权。

分析

看到最小生成树考虑采用 Kruskal, Prim, Boruvka 的一种。
这道题采用 Kruskal 即可。

根据 Kruskal 的过程，每次取出最小的 aka_k，连上所有可能的边。我们考虑如何快速求出每个 aka_k 的贡献。

做法 1（二分）

根据均摊我们知道，总共只会连上 n−1n-1 条边。
如果我们能够花费一定的代价，快速求出下一个能连上的边，就能解决本题。

采用并查集，维护一个序列，每个位置的值是它在并查集中的代表元素。
假设当前处理的是 aka_k，每次连接的是以 k/2k/2 为中心的一个区间，如果 [l,r] (l+r=k)[l,r]\ (l+r=k) 内的都已经连上了，反映在序列中就是 [l,r][l,r] 是回文串，而这个显然是有单调性的，每次二分找到最长的已经连接完的长度，然后连上一条新的边，均摊复杂度正确。

那么我们只需要采用树状数组维护哈希，启发式合并并查集中的元素，即可 O(nlog⁡2n)O(n\log^2 n) 解决本题。

关于树状数组维护哈希，每个位置带权 bxb^x 即可简单地维护，查询的时候统一长度，至于维护回文串，再开一个树状数组维护反串即可（当然可以用线段树，只是树状数组常数比较小）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int MOD = 1e9+7;
const int B   = 19260817;

const int N = 2e5+5;
inline int lowbit(int x){return x&-x;}

int n;

int bp[N];
struct BIT{
    int t[N];
    void add(int x,int v){
        v = (v+MOD)%MOD; v = (ll)v*bp[x]%MOD;
        for(int i=x;i<=n;i+=lowbit(i))t[i]=(t[i]+v)%MOD;
    }
    int query(int r){
        int ans = 0;
        for(int i=r;i;i-=lowbit(i))ans=(ans+t[i])%MOD;
        return ans;
    }
    int query(int l,int r){
        int res = (query(r)-query(l-1)+MOD)%MOD;
        return (ll)res*bp[n-r]%MOD;
    }
}t1,t2;
void add(int i,int j){
    t1.add(i,j);
    t2.add(n-i+1,j);
}
bool is_palindrome(int l,int r){
    return t1.query(l,r) == t2.query(n-r+1,n-l+1);
}


vector<int> v[N];
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unite(int i,int j){
    i = find(i), j = find(j);
    if(i==j)return;
    if(v[i].size() < v[j].size())swap(i,j);
    for(auto x:v[j]){
        v[i].push_back(x);
        add(x,i-j);
    }
    fa[j]=i; v[j].clear();
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    bp[0]=1;
    for(int i=1;i<N;i++)bp[i]=(ll)bp[i-1]*B%MOD;
    
    cin>>n;
    vector<pair<int,int>> a;
    for(int i=3;i<=2*n-1;i++){
        int x;cin>>x;
        a.push_back({x,i});
    }
    sort(a.begin(),a.end());

    for(int i=1;i<=n;i++){
        fa[i]=i; add(i,i);
        v[i].push_back(i);
    }

    ll ans = 0;
    for(auto [val,k]:a){
        int m1 = (k-1)/2;
        int m2 = k/2+1;
        int len = min(m1, n-m2+1);
        int l=1;
        while(l<=len){
            int r = len+1;
            while(l<r){
                int mid = (l+r)>>1;
                if(is_palindrome(m1-mid+1,m2+mid-1))l=mid+1;
                else r=mid;
            }
            if(l>len)break;
            unite(m1-l+1,m2+l-1);
            ans += val;
        }
    }

    cout << ans << '\n';

    return 0;
}

做法 2（倍增）

部分参考自 https://www.cnblogs.com/binbin200811/p/18698464。

我们把原串反过来复制一遍放在后面，这样 [l,r][l,r] 是回文串的条件就能等价转换为 [l,r]=[2n−r+1,2n−l+1][l,r]=[2n-r+1,2n-l+1]。

问题转化为：给定一个序列，每次告诉你两段区间内容相等，求新连了几条边（也就是少了几个等价类）。

不难发现这就是 [SCOI2016] 萌萌哒 的动态版。考虑同样进行倍增，建立 kk 个长度为 2n2n 的并查集，若在第 i (0≤i<k)i\ (0\le i<k) 个并查集中 xx 和 yy 是等价的，说明区间 [x,x+2i−1][x,x+2^i-1] 和 [y,y+2i−1][y,y+2^i-1] 相等。

初始需要把第 00 个并查集的 ii 和 2n−i+12n-i+1 连起来，表示反过来放在后面的意思。

接下来每个区间都能被拆成 O(log⁡(r−l+1))O(\log(r-l+1)) 段。假设我们要在第 kk 个并查集将 x,yx,y 连起来，记这样的操作为 (k,x,y)(k,x,y)，分类讨论：

  • 若 x,yx,y 本来就在 kk 中连起来了，直接返回。
  • 若 x,yx,y 没有在 kk 中连起来，连接 (x,y)(x,y)，然后：
    • 若 k=0k=0，答案加上这一次的边权，返回。（多连了一条边）
    • 否则，递归处理 (k−1,x,y)(k-1,x,y),(k−1,x+2k−1−1,y+2k−1−1)(k-1,x+2^{k-1}-1,y+2^{k-1}-1)。

这个算法的正确性在于两点：

  1. 我们保证了时刻若第 kk 个并查集 (x,y)(x,y) 相连，第 k−1k-1 个并查集 (x+2k−1−1,y+2k−1−1)(x+2^{k-1}-1,y+2^{k-1}-1) 相连。（保证往下全部相连，这样如果前面已经连了可以直接返回，不用考虑往下递归）
  2. 每次递归都至少保证父亲连上了边（不考虑初次递归），而最多只有 22 个节点会共用一个父亲，总共只有 O(nlog⁡n)O(n\log n) 条边能连，所以均摊复杂度为 O(nlog⁡n)O(n\log n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N = 4e5+5;
int n;
struct DSU{
    int fa[N];
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    void unite(int i,int j){
        i = find(i), j = find(j);
        if(i==j)return;
        fa[j]=i;
    }
}d[20];

ll ans = 0;
void merge(int dep,int i,int j,int w){
    if(d[dep].find(i) == d[dep].find(j))return;
    if(!dep){
        d[dep].unite(i,j);
        ans += w;
        return;
    }
    d[dep].unite(i,j);
    merge(dep-1, i, j, w);
    merge(dep-1, i+(1<<(dep-1)),j+(1<<(dep-1)), w);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>n;
    vector<pair<int,int>> a;
    for(int i=3;i<=2*n-1;i++){
        int x;cin>>x;
        a.push_back({x,i});
    }
    sort(a.begin(),a.end());

    for(int i=1;i<=n*2;i++)for(int j=0;j<20;j++)d[j].fa[i]=i;
    for(int i=1;i<=n;i++)d[0].unite(i,2*n-i+1);
    
    for(auto [val,k]:a){
        int m1 = (k-1)/2, m2 = k/2+1;
        int len = min(m1, n-m2+1);
        int l = m1-len+1, r = m2 + len - 1; // [l,r] 是回文串
        len = r-l+1;
        for(int i=0;i<20;i++){
            if((len>>i)&1){
                len ^= (1 << i);;
                merge(i, l+len, 2*n-r+1+len, val);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

练习

  • P3295 [SCOI2016] 萌萌哒
  • QOJ# 4998. Keyboard Queries
    这题因为要随时回答 [l,r][l,r] 是否等于 [l′,r′][l',r']，如果用倍增还需一个数据结构动态维护哈希，套启发式并查集。
    所以二分（做法 1）复杂度为 O(qlog⁡n⋅(查询复杂度+修改复杂度))O(q\log n\cdot(\text{查询复杂度} + \text{修改复杂度}))，倍增（做法 2）复杂度为 O(nlog⁡n⋅修改复杂度+q⋅查询复杂度)O(n\log n \cdot \text{修改复杂度} + q\cdot \text{查询复杂度})。