↵
We have elements on which we need to perform two types of queries:↵
↵
1. Union — merge the sets containing elements
↵
У нас есть элементы, над которыми нужно выполнять два типа запросов:↵
↵
1. Union — объединить множества, содержащие элементы v1
2. Add —
↵
↵
For an add query, we find the root of the tree containing vertex v and add the modification to that root.↵
When we need to get the actual value of a[i], we first compress the path to the root and apply the root’s modification. During path compression (in the recursive process of reattaching the nodes), we also apply the parent’s modification to the current node.↵
↵
For the union operation, we can either:↵
↵
1. create a new virtual node to act as the parent of both components
↵
При запросе Add мы находим корень дерева, содержащего вершину v, и добавляем модификацию в этот корень.↵
Когда нужно получить реальное значение a[i], мы сначала выполняем сжатие пути к корню и применяем модификации от корня.↵
Во время сжатия пути (в процессе рекурсивного переподключения вершин) мы также применяем модификацию родителя к текущей вершине.↵
↵
Для операции Union можно действовать двумя способами:↵
↵
1. Создать новую виртуальную вершину, которая станет родителем обоих компонентов.↵
↵
The second approach is a bit trickier to implement when the modifications are more complex.↵
↵
code:
↵
Второй способ немного сложнее в реализации, особенно если модификации более сложные.↵
↵
<spoiler summary="Spoiler">↵
~~~~~↵
void apply(int v, long long add) {↵
res[v] += add;↵
lazyAdd[v] += add;↵
}↵
↵
int getPar(int v) {↵
if (v == comp[v]) return v;↵
int p = getPar(comp[v]);↵
if (comp[v] != p) apply(v, lazyAdd[comp[v]]);↵
return comp[v] = p;↵
}↵
↵
long long getVal(int v) {↵
int p = getPar(v);↵
if (v == p) return res[v];↵
return res[v] + lazyAdd[p];↵
}↵
↵
void add(int v, long long x) {↵
v = getPar(v);↵
apply(v, x);↵
}↵
↵
void unionSet(int v1, int v2) {↵
v1 = getPar(v1);↵
v2 = getPar(v2);↵
if (v1 == v2) return;↵
↵
int p = ++allNodes;↵
comp[v1] = p;↵
comp[v2] = p;↵
↵
res[p] = 0;↵
lazyAdd[p] = 0;↵
sz[p] = sz[v1] + sz[v2] + 1;↵
}↵
~~~~~↵
</spoiler>↵
↵
