专栏文章

题解：P12736 [POI 2016 R2] 圣诞灯链 Christmas chain

AAnhe
P12736题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip3vpdn
此快照首次捕获于
2025/12/03 05:44
3 个月前
此快照最后确认于
2025/12/03 05:44
3 个月前
查看原文

并查集 + 倍增

助人为乐，顺便写个题解。

题目分析

题目要求在满足所有指定两个灯链片段颜色完全相同的前提下，求灯链中最大不同颜色数。
条件等同于 ai+ja_i+j 与 bi+jb_i+j 颜色相同（0≤j<li0\le j<l_i）。将灯泡视为节点，每个条件为节点间连边，则最终连通块内的节点颜色必须相同，不同连通块可赋予不同颜色。最大颜色数即为连通块数量。
但由于 n,m≤500000n,m≤500000，直接建图显然不行。
考虑使用并查集和倍增优化。
将每个位置拆分为 k=log⁡nk=\log n 层，每层对应 2k2^k 长度的区间。每层维护独立并查集,并按秩合并。
第 00 层联通块的个数即为答案，时间复杂度约 O((n+m)log⁡n⋅α(n))O((n+m)\log n⋅α(n))（α(n)α(n) 为并查集反阿克曼函数）。
完结撒花！

具体细节见代码

CPP
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;  // 2^20 > 500000

int fa[LOG][MAXN];
int rnk[LOG][MAXN];
int n, m;

//查找 
int find(int k, int x) {
    int root = x;
    while (fa[k][root] != root) {
        root = fa[k][root];
    }
    int temp = x;
    while (fa[k][temp] != root) {
        int nxt = fa[k][temp];
        fa[k][temp] = root;
        temp = nxt;
    }
    return root;
}

// 合并
void merge(int k, int x, int y) {
    int fx = find(k, x);
    int fy = find(k, y);
    if (fx == fy) return;
    if (rnk[k][fx] < rnk[k][fy]) {
        fa[k][fx] = fy;
    } else if (rnk[k][fx] > rnk[k][fy]) {
        fa[k][fy] = fx;
    } else {
        fa[k][fy] = fx;
        rnk[k][fx]++;
    }
}

int main() {
    scanf("%d %d", &n, &m);

    for (int k = 0; k < LOG; k++) {
        for (int i = 1; i <= n; i++) {
            fa[k][i] = i;
            rnk[k][i] = 0;
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, l;
        scanf("%d %d %d", &a, &b, &l);
        int k = 0;
        while ((1 << (k+1)) <= l) {
            k++;
        }
        merge(k, a, b);
        int pos1 = a + l - (1 << k);
        int pos2 = b + l - (1 << k);
        merge(k, pos1, pos2);
    }

    for (int k = LOG-1; k >= 1; k--) {
        int mid = 1 << (k-1);
        for (int i = 1; i <= n; i++) {
            int root = find(k, i);
            merge(k-1, i, root);
            if (i + mid <= n && root + mid <= n) {
                merge(k-1, i + mid, root + mid);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (find(0, i) == i) {
            ans++;
        }
    }
    printf("%d\n", ans);

    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...