Static Range Union Find

N頂点のUnion Findが与えられます。以下のクエリがQ個与えられます。

• given l, r, dist: merge(l, r), merge(l+1, r+1), merge(l+2, r+2), ..., merge(l+dist, r+dist)

これを処理した後のUnion Findを計算してください

これは D: LCP(prefix,suffix) - 「みんなのプロコン 2018」決勝 | AtCoder の本質部分です(ネタバレ)

O(N α(N) + Q)で解けます。

Submission #8391439 - 「みんなのプロコン 2018」決勝 | AtCoder