DSU: O*(1) <--- Амор.

DSU: O(logn) <--- в худшем

Persistent-DSU: O(log^2n)

Persistent Array в Offline
O(1)

version #i : a[j] <-- x (new version #k++)
Change(i, j, x)
Get(i, j)

1. BuildTree
2. dfs

i --(j,x)--> k

будем dfs обходить дерево версий

dfs(i)
  int old = a[j]
  a[j] = x
  dfs(k)
  a[j] = old