「JOI 2023 Final」石子排列 2 题解

题目大意

有 $N$ 个石子，每个石子有一个颜色 $A_i$。按顺序进行 $N$ 次操作：

1. 将石子 $i$ 放在序列末尾
2. 如果之前存在颜色为 $A_i$ 的石子，找到最近的一个位置 $j$，将区间 $[j+1, i-1]$ 的所有石子染成颜色 $A_i$

求所有操作完成后每个石子的颜色。

解题思路

核心观察

1. 染色范围的确定性：当石子 $i$ 被放置时，它会影响从上一次出现相同颜色的下一个位置到 $i-1$ 的所有石子
2. 最终颜色由最后一次染色决定：每个位置的颜色由最后一次覆盖它的操作决定
3. 关键性质：对于颜色 $A_i$，它会影响从位置 $i$ 开始，直到该颜色下一次出现之前的所有位置

算法解析

1. 预处理最后出现位置

map<int, int> last;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    last[a[i]] = i;  // 记录每个颜色最后出现的位置
}

2. 跳跃染色

for (int i = 1; i <= n; i++) {
    int j = i;
    for (; j <= last[a[i]]; j++)  // 染色直到该颜色最后出现的位置
        ans[j] = a[i];
    i = j - 1;  // 跳跃到已处理的位置
}

算法正确性证明

为什么这样染色是正确的？

对于每个颜色 $A_i$：

• 它会在位置 $i$ 被放置
• 根据规则，它会染色从上次出现位置+1到 $i-1$ 的区间
• 但更重要的是：在位置 $i$ 之后，直到该颜色下一次出现之前的所有位置，都可能被这个颜色影响

实际上，这个解法利用了以下关键性质：

• 一旦在位置 $i$ 放置颜色 $c$，那么从 $i$ 开始直到颜色 $c$ 下一次出现之前的所有位置，最终都会被染成颜色 $c$
• 通过预处理每个颜色的最后出现位置，我们可以一次性处理整个区间

复杂度分析

• 时间复杂度：$O(N)$
  • 虽然看起来是双重循环，但内层循环的 i = j - 1 确保了每个位置只被处理一次
  • 外层循环的 i 会直接跳到已处理区间的末尾
• 空间复杂度：$O(N)$

样例分析

样例1：

输入: [1, 2, 1, 2, 3, 2]
预处理last: {1:3, 2:6, 3:5}

处理过程：
i=1: 颜色1, last[1]=3 → 染色[1,3] → ans=[1,1,1,?,?,?], i跳到3
i=4: 颜色2, last[2]=6 → 染色[4,6] → ans=[1,1,1,2,2,2], i跳到6
结束

输出: [1,1,1,2,2,2]

样例2：

输入: [1,1,2,2,1,2,2,1,1,2]
预处理last: {1:9, 2:10}

处理过程：
i=1: 颜色1, last[1]=9 → 染色[1,9] → ans=[1,1,1,1,1,1,1,1,1,?], i跳到9
i=10: 颜色2, last[2]=10 → 染色[10,10] → ans=[1,1,1,1,1,1,1,1,1,2]
结束

输出: [1,1,1,1,1,1,1,1,1,2]

算法优势

1. 高效性：$O(N)$ 时间复杂度，处理 $2\times 10^5$ 数据毫无压力
2. 简洁性：代码非常简洁，核心部分只有几行
3. 正确性：利用了题目的特殊性质，避免复杂的模拟

关键洞察

这个解法的核心在于认识到：

• 不需要模拟每一步的染色过程
• 每个颜色会"统治"从它出现位置到下一个同色位置之间的区间
• 通过预处理最后出现位置，可以一次性确定每个区间的最终颜色

总结

本题展示了一种高效的解题思路：通过分析操作的本质特性，找到规律，从而避免复杂的逐步模拟。这种"跳跃处理"的思想在很多区间操作问题中都很有效。

关键技巧：

1. 预处理关键信息（最后出现位置）
2. 利用跳跃指针避免重复处理
3. 从整体角度分析操作的影响范围