找颜色不同前驱

dottle · 2025-02-07 16:04:51 · 算法·理论

在 Borůvka 算法中，会遇到这样的问题：

• 在序列上每个点有一个颜色，你需要找到一个数前面第 k 个和它颜色不一样的点。时间复杂度要求 O(k)。

预处理一个数组 pr_i 表示 i 前一个和它颜色不一样的点。计算时考察 i 和 i-1 颜色是否一样，若否则 pr_i=i-1；否则等于 pr_{i-1}。

要找第二个和它颜色不一样的点，只需对 pr_i-1 进行同样的分析即可。