浅谈类并查集链表

Nicrobot · 2023-11-30 14:05:40 · 个人记录

名字是不知道哪里看到的，如果不对请吱一声。

类并查集链表是一种奇怪的数据结构。

它通常用于维护一个序列内的标记信息：

1. 将一个被标记的数字取消标记。
2. 查询某数右侧第一个被标记的数字。
3. 遍历一个区间 [l,r] 内所有未被标记的数字

则可以使用类并查集链表解决。其前两种均摊每次时间复杂度与并查集相同，即 O(\log n)（路径压缩）；或 O(\alpha(n))（路径压缩+按秩合并）。第三种则需要乘以当前被标记的数的个数 cnt。因此它通常适用于“修改及访问次数有一定限制”的操作。

我们对于每个数维护一个指针 p_i 表示自己以及右边第一个被标记的数字。若 i 被标记，令 p_i=i，否则 p_i=i+1。则对 p 数组进行并查集的 find 操作就能实现第二种操作。

当进行第一种操作时，也是直接令 p_i=i+1，执行 find(i+1) 操作就找到了。

遍历区间，只需在开始时，令 t=find(l)，每次访问完 t 这个位置，就令 t=find(t+1)，循环直至 t>r。

显然路径压缩可以使用，相当于一个退化的并查集，均摊 find() 时间复杂度不会超过 O(\log n)，但仍然可以通过构造达到。

至于按秩合并需要一些技巧（因为指的方向会改变）那就咕咕一下。

code：

struct DSU {
    int fa[N], co[N];
    int sz;

    void init(int x) {
        sz = x;
        for (int i = 1; i <= x; i++) fa[i] = i; // 这里初始都打上了标记。
    }

    int findfa(int x) {
        if (fa[x] == x) return x;
        return fa[x] = findfa(fa[x]);
    }
    void solve(int type, int l, int r, int k) {
        for (int i = findfa(l); i <= r; i = findfa(i + 1)) {
            // 维护信息，然后删除 i 的标记
            fa[i] = findfa(i + 1);
        }
    }
};

例题 1： P9715 头

这里本来应该有个头的图片。可惜被和谐了。

你有一个 n 行 m 列的网格，所有格子上都没有颜色。有 k 种颜色的刷子，颜色编号为 1\sim k。然后给出 q 次操作，每次操作给出 op,l,r,c,t 五个参数：

• 如果 op=1，表示将第 l\sim r 行的所有格子涂成颜色 c。
• 如果 op=2，表示将第 l\sim r 列的所有格子涂成颜色 c。
• 如果 t=0，意味着如果涂色时遇到已经被染色的格子，就不再进行染色。
• 如果 t=1，意味着如果涂色时遇到已经被染色的格子，就用新的颜色覆盖它。

在所有涂色操作结束以后，对于每种颜色，求出有多少个格子被染成了这种颜色。