POI2016 R2 圣诞灯链 题解

题目理解

我们有一个长度为 $n$ 的灯链，有 $m$ 个约束条件，每个约束条件表示两个长度相同的区间必须颜色完全相同。

目标是：在满足所有约束条件的情况下，让灯链中出现的不同颜色数量尽可能多。

问题转化

设灯链中位置 $i$ 的颜色为 $c_i$，每个约束条件 $(a,b,l)$ 表示：

$$c_{a+k} = c_{b+k} \quad \text{对于所有 } 0 \leq k < l$$

我们需要找出所有这样的等价关系，将必须相同颜色的位置合并到同一个等价类中。最终不同等价类的数量就是最大颜色数。

核心思路

倍增分解

对于任意区间 $[x, x+l-1]$，我们可以将其分解为若干个长度为 $2^k$ 的区间：

• 找到最大的 $k$ 满足 $2^k \leq l$
• 区间 $[x, x+l-1]$ 可以表示为：
  • $[x, x+2^k-1]$（长度为 $2^k$）
  • $[x+l-2^k, x+l-1]$（长度为 $2^k$）

这样，任何区间约束都可以用 $O(\log n)$ 个长度为 $2^k$ 的区间约束来表示。

分层并查集设计

我们设计一个 $19$ 层的并查集（因为 $n \leq 500,000 < 2^{19}$）：

• 第 $j$ 层处理所有长度为 $2^j$ 的区间约束
• fa[j][i] 表示在第 $j$ 层中，从位置 $i$ 开始的长度为 $2^j$ 的区间所属的集合

算法步骤

1. 初始化并查集

dsu.init(n);  // 初始化所有层的并查集，每个位置独立成集合

2. 处理约束条件

对于每个约束 $(a, b, l)$：

int k = __lg(l);  // 最大的k满足2^k ≤ l
// 合并[a, a+2^k-1]与[b, b+2^k-1]
dsu.merge(k, a, b);
// 合并剩余部分[a+l-2^k, a+l-1]与[b+l-2^k, b+l-1]  
dsu.merge(k, a + l - (1 << k), b + l - (1 << k));

3. 约束传递（关键步骤）

从高层向低层传递约束关系：

for j from 18 down to 1:
    for i from 1 to n - (1 << j) + 1:
        dsu.pushdown(j, i);

pushdown 操作的含义：

• 如果在第 $j$ 层，区间 $[x, x+2^j-1]$ 和 $[y, y+2^j-1]$ 颜色相同
• 那么在第 $j-1$ 层：
  • 前半段 $[x, x+2^{j-1}-1]$ 和 $[y, y+2^{j-1}-1]$ 颜色相同
  • 后半段 $[x+2^{j-1}, x+2^j-1]$ 和 $[y+2^{j-1}, y+2^j-1]$ 颜色相同

4. 统计答案

int ans = 0;
for i from 1 to n:
    if i == dsu.find(0, i):  // 在第0层找根节点
        ans++;
cout << ans << endl;

正确性分析

完备性

每个约束条件都被正确处理：通过倍增分解，任意长度 $l$ 的区间都可以用 $O(\log n)$ 个长度为 $2^k$ 的区间精确覆盖。

正确性

约束传递确保等价关系完整传播：高层的大区间约束被正确分解为低层的小区间约束。

最优性

不同连通分量之间没有约束关系，可以使用不同颜色，因此连通分量数量就是最大颜色数。

时间复杂度分析

• 预处理：$O(n \log n)$ 初始化分层并查集
• 处理约束：每个约束 $O(\log n)$ 时间，共 $O(m \log n)$
• 约束传递：$O(n \log n)$
• 统计答案：$O(n)$

总时间复杂度：$O((n + m) \log n)$，在题目数据范围内完全可行。

样例分析

样例1

输入：10 3
1 6 3
5 7 4  
3 8 1
输出：3

处理过程：

1. 约束 $(1,6,3)$：位置1-3与6-8颜色相同
2. 约束 $(5,7,4)$：位置5-8与7-10颜色相同
3. 约束 $(3,8,1)$：位置3与8颜色相同
4. 最终形成3个等价类：$\{1,3,5,6,8,10\}$、$\{2,7,9\}$、$\{4\}$

样例2

输入：4 2
1 2 2
2 3 2
输出：1

所有位置都被约束为相同颜色，只能使用1种颜色。

算法实现细节

并查集操作

struct Dsu {
    int fa[19][N];  // 分层并查集
    
    void init(int n) {
        for(int j = 0; j <= 18; j++)
            for(int i = 1; i <= n - (1 << j) + 1; i++)
                fa[j][i] = i;
    }
    
    int find(int j, int i) {
        return i == fa[j][i] ? i : fa[j][i] = find(j, fa[j][i]);
    }
    
    bool merge(int j, int x, int y) {
        x = find(j, x);
        y = find(j, y);
        if(x == y) return false;
        fa[j][x] = y;
        return true;
    }
    
    void pushdown(int j, int x) {
        if(x == find(j, x)) return;
        // 传递到下一层的两个对应区间
        merge(j - 1, x, find(j, x));
        merge(j - 1, x + (1 << (j - 1)), find(j, x) + (1 << (j - 1)));
    }
};

算法优势

1. 高效性：将 $O(n)$ 的区间合并转化为 $O(\log n)$ 的倍增操作
2. 可扩展性：适用于大规模数据（$n, m \leq 500,000$）
3. 简洁性：代码实现相对简洁，主要逻辑清晰

算法标签

• 并查集
• 倍增技巧
• 区间处理
• 图论连通分量

总结

这道题的核心在于如何高效处理区间相等约束。通过分层并查集和倍增技巧，我们成功地将看似复杂的区间合并问题转化为可高效求解的连通分量问题，最终通过统计连通分量数量得到最大颜色数。