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)で解けます。
N頂点のUnion Findが与えられます。以下のクエリがQ個与えられます。
これを処理した後のUnion Findを計算してください
これは D: LCP(prefix,suffix) - 「みんなのプロコン 2018」決勝 | AtCoder の本質部分です(ネタバレ)
O(N α(N) + Q)で解けます。