概要

問題へのリンク

公式解説 は，ちゃんと読んでいない．

ユーザ解説 で紹介されている解法を読んだ．

次の2つのクエリを処理するものを，Range Parallel Unionfind (仮称) というらしい

  • merge(a, b, l) : $i \in [0, l)$ について，頂点 $a + i$ と 頂点 $b + i$ の間に辺を結ぶ．
  • leader(a) : 頂点 $a$ を含む連結成分の代表元を返す．

この問題は，次のように解ける．

  1. $2N$ 頂点のグラフを考える．
    • 気持ちは，前半が $S$ で，後半が $S$ を逆順にしたもの
  2. 各 $i$ に対して，回文になるために必要なところ (前半と後半を使う) を線で結ぶ． これは，上の Range Parallel Unionfind の merge(a, b, l) でできる．
  3. 頂点 $i$ と $2*N - 1 - i$ を線で結ぶ．これは普通の Unionfind を使う．
  4. 回文の一つ外側の文字どうしが同じ連結成分に入っていたら不可能． そうでなければ，辞書順最小のものを求めるために，貪欲に各連結成分の値を決めていく．

ということで，Range Parallel Unionfind なるものができれば良い．2つ紹介されている．

アルゴリズム1

ノード数$N$，クエリ数$Q$ として，時間計算量 $O((N + Q)\log^2 N)$． こちらは，2つのクエリが混ざってきても良い．

普通の UnionFind も使う．leader は，普通の leader を使う．

各ノード $i$ が属する連結成分の代表元を $p(i)$ と書くことにする． $p$ のローリングハッシュを計算するセグメント木を用意する． merge(a, b, l) が来たときに，$p[a:a + l)$ と $p[b:b + l)$ が一致していれば何もしなくて良い． 一致していなければ，二分探索をして $p[a + i] \neq p[b + i]$ である $i$ が見つけられる． $a + i$ と $b + i$ を (普通に) merge して，もともと小さかった連結成分の方の $p$ を更新する．

アルゴリズム2

時間計算量 $(N \alpha(N))$． こちらは，merge が全部すんでから leader が来るという前提．

$a_k + i$ と $b_k + i$ の merge を，$l_k - i$ の大きい順に行う． つまり，残っている列の長い順に行っていく． すると，ある時点で $a_k + i$ と $b_k + i$ が同じ連結成分に属していたら， $j > i$ に対する $a_k + j$ と $b_k + j$ の組は見る必要が無い． $a_k + i$ と $b_k + i$ が同じ連結成分になるのと同じ理由で，同じ連結成分に入っているはずである．