并查集维护序列段

Claire0918 · 2025-01-05 21:38:09 · 算法·理论

例题：P1840。有 \mathcal{O}(n \log n) 的线段树朴素做法，这里不给出。

考虑记 p_i 表示 i 及 i 前首个黑点，即最大的 j \leq i 使得第 j 个点为黑点。

这时，如果 i 是黑点，就有 p_i = i，否则 p_i < i。如果我们希望求得 i 前首个黑点，我们可以重复置 i \gets p_i，直到 p_i = i，此时 i 就是黑点。

初始时，每个点都是黑点，即 (\forall i \in [1, n])(p_i \gets i)。

对于 [l, r] 染色时，从 r 开始，将当前黑点 i 染白，然后置 p_i \gets i - 1，随后通过上文的方式找到 i 前首个黑点 j，置 i \gets j。重复以上染色操作，直到 i < l。

直接操作单次跳复杂度可以达到 \mathcal{O}(n)，注意到跳上一个黑点和将 p_i 挂到一个点上的过程非常类似并查集，所以可以对 p_i 使用路径压缩优化，即可做到单次跳 \mathcal{O}(\alpha(n))。

不难发现每个点最多被染色 1 次，即最多被跳到 1 次，所以总复杂度为 \mathcal{O}(n\alpha(n))，非常优秀。

实现：

int main(){
    scanf("%d %d", &n, &q);
    iota(father, father + n + 1, 0);
    while (q--){
        int l, r;
        scanf("%d %d", &l, &r);
        r = get_f(r);
        while (r >= l){
            n--;
            father[r] = r - 1;
            r = get_f(r);
        }
        printf("%d\n", n);
    }

return 0;
}

应用：P4145。

根号取下整可以快速变成 1，此时就不必再对其进行操作。我们需要对于一个点跳到上一个非 1 的点进行操作，可以使用上文的并查集维护序列段。

注意上一题每一次都会执行 p_i \gets i - 1，所以可以直接从 i 开始跳；但本题中当前位置没有变成 1 时不会执行 p_i \gets i - 1，所以我们应当从 i - 1 开始跳。

实现：

r = get_f(r);
while (r >= l){
    const int temp = sqrt(a[r]);
    add(r, temp - a[r]);
    if ((a[r] = temp) == 1){
        father[r] = r - 1;
    }
    r = get_f(r - 1);
}