Can I change the solution to the DSU painting subarrays question?

101 views Asked by At

The link to the post about this algorithm which I have a question for is here: https://cp-algorithms.com/data_structures/disjoint_set_union.html

My question is specifically about this section

We have a segment of length  $L$ , each element initially has the color 0. We have to repaint the subarray  $[l, r]$  with the color  $c$  for each query  $(l, r, c)$ . At the end we want to find the final color of each cell. We assume that we know all the queries in advance, i.e. the task is offline.

The solution is

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;
    }
}

My confusion lies in parent[v] = v + 1. How I thought about this question is that we should instead do parent[v] = parent[v] + 1. Since we can assume that everything between v and parent[v] are already painted.

From my testing, it seems that this change doesn't change the answer but I'm not sure if I might be missing some edge cases.

Would it be correct for me to write parent[v] = parent[v] + 1 and are there any implications for the time complexity if I were to make this change?

0

There are 0 answers