关于DSU离线子数组染色问题的代码修改疑问及复杂度咨询

问题背景 #

给定长度为$L$的线段，初始所有元素颜色为0，需处理若干离线查询$(l, r, c)$，将子数组$[l, r]$染为颜色$c$，最终求每个位置的颜色。原解法采用并查集（DSU）倒序处理查询，核心代码如下：

void make_set(int v) {
    parent[v] = v;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

for (int i = 0; i <= L; i++) {
    make_set(i);
}

for (int i = m-1; i >= 0; i--) {
    int l = query[i].l;
    int r = query[i].r;
    int c = query[i].c;
    for (int v = find_set(l); v <= r; v = find_set(v)) {
        answer[v] = c;
        parent[v] = v + 1;
    }
}

关于parent[v] = v + 1的修改分析 #

1. 修改是否正确？ #

你提出的parent[v] = parent[v] + 1在当前算法逻辑下完全正确，和原代码效果完全一致，不存在边缘case差异。

原因很简单：在循环中，v是find_set(l)的返回值，而find_set的返回值是当前节点的根节点——根节点的parent值必然等于自身（parent[v] = v）。所以此时parent[v] + 1等价于v + 1，两种写法执行结果没有区别。

2. 对时间复杂度的影响？ #

两种写法的时间复杂度完全相同，都是近似$O(L \alpha(L))$（$\alpha$是阿克曼函数的反函数，增长极慢，可视为常数）。

这个算法的核心是每个位置只会被染色一次，每次find_set操作通过路径压缩保证了近乎常数的时间。不管是直接赋值v+1还是parent[v]+1，因为赋值时parent[v]等于v，所以操作的时间开销完全一致，不会改变整体的时间复杂度。

内容的提问来源于stack exchange，提问作者flameshooter09