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

__liujy · 2026-04-25 18:12:56 · 题解

这个 trick 是不是已经烂大街了。

下面对于一次美学要求，记为 (a, b, l)。

对于 (a, b, l) 需要相等的两个区间 [a, a + l - 1] 与 [b, b + l - 1]，可以划分成若干个区间，具体可以看下面两张图：

红色的是原始序列，蓝色和紫色分别是可以被分割的区域，而灰色不行，因为红色序列中有一段区间没有被包含到。

分成两个区间比较方便，接下来考虑如何分成两个区间。

这两个区间取 2 的整数次方比较好操作，然后类似于 ST 表的处理方式做一下就行了。

#include<bits/stdc++.h>
const int MAXN = 500000 + 5, MAXM = 20;
int n, q;
int lg[MAXN], fa[MAXN][MAXM], mi[MAXN], mx[MAXN];
inline void init()
{
    lg[0] = -1;
    for(int i = 1; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; i++)
        fa[i][0] = i;
    for(int j = 1; j <= lg[n]; j++)
        for(int i = 1; i <= n; i++)
            fa[i][j] = i;
    for(int i = 1; i <= n; i++)
        mi[i] = mx[i] = i;
}
inline int getf(int x, int s)
{
    if(fa[x][s] == x) return x;
    return fa[x][s] = getf(fa[x][s], s);
}
inline void modify(int l, int r, int s)
{
    int xf = getf(l, s), yf = getf(r, s);
    if(xf == yf) return;
    fa[xf][s] = yf;
    if(!s)
    {
        mi[yf] = std::min(mi[yf], mi[xf]);
        mx[yf] = std::max(mx[yf], mx[xf]);
        return;
    }
    modify(l, r, s - 1), modify(l + (1 << (s - 1)), r + (1 << (s - 1)), s - 1);
}
int main()
{
    scanf("%d%d", &n, &q);
    init();
    for(int _ = 1, a, b, l; _ <= q; _++)
    {
        scanf("%d%d%d", &a, &b, &l);
        int s = lg[l];
        modify(a, b, s);
        modify(a + l - (1 << s), b + l - (1 << s), s);
    }
    std::map<int, int> M;
    for(int i = 1; i <= n; i++)
        M[getf(i, 0)]++;
    printf("%d\n", M.size());
    return 0;
}