我可以更改 DSU 绘制子数组问题的解决方案吗？

Question

有关该算法的帖子的链接（我有疑问）在这里：https://cp-algorithms.com/data_structs/disjoint_set_union.html

我的问题专门针对此部分

我们有一个长度为  $L$  的线段，每个元素最初的颜色为 0。对于每个查询  $(l, r, c)$，我们必须使用颜色  $c$  重新绘制子数组  $[l, r]$ 。最后我们想要找到每个单元格的最终颜色。我们假设我们提前知道所有查询，即任务是离线的。

解决办法是

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

。我对这个问题的想法是我们应该做

parent[v] = parent[v] + 1

。因为我们可以假设 v 和 Parent[v] 之间的所有内容都已绘制。

从我的测试来看，这种变化似乎并没有改变答案，但我不确定我是否可能遗漏了一些边缘情况。

我这样写

parent[v] = parent[v] + 1

是否正确？如果我进行此更改，会对时间复杂度产生任何影响吗？

Answer 1

是的，因为

find_set()

在

v == parent[v]

时终止，所以在内层for循环中，对于每一个

v

，我们都有

v == parent[v]

，所以我们可以互换使用它们，时间复杂度不会改变。

您可以在内层 for 循环的开头添加

assert(v == parent[v]);

来确认。