概要
公式解説 は，ちゃんと読んでいない．
ユーザ解説 で紹介されている解法を読んだ．
次の2つのクエリを処理するものを，Range Parallel Unionfind (仮称) というらしい
merge(a, b, l): $i \in [0, l)$ について，頂点 $a + i$ と 頂点 $b + i$ の間に辺を結ぶ．leader(a): 頂点 $a$ を含む連結成分の代表元を返す．
この問題は，次のように解ける．
- $2N$ 頂点のグラフを考える．
- 気持ちは，前半が $S$ で，後半が $S$ を逆順にしたもの
- 各 $i$ に対して，回文になるために必要なところ (前半と後半を使う) を線で結ぶ．
これは，上の Range Parallel Unionfind の
merge(a, b, l)でできる． - 頂点 $i$ と $2*N - 1 - i$ を線で結ぶ．これは普通の Unionfind を使う．
- 回文の一つ外側の文字どうしが同じ連結成分に入っていたら不可能． そうでなければ，辞書順最小のものを求めるために，貪欲に各連結成分の値を決めていく．
ということで，Range Parallel Unionfind なるものができれば良い．2つ紹介されている．
アルゴリズム1
ノード数$N$，クエリ数$Q$ として，時間計算量 $O((N + Q)\log^2 N)$??． こちらは，2つのクエリ (merge, leader) が混ざってきても良い．
連結成分の集合を取得できる UnionFind を使う．
各ノード $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 する．代表元が更新された方の旧連結成分要素に対して，
セグメント木の値を更新する．残りの $[i + 1, l)$ についても同様に繰り返す．
アルゴリズム2
時間計算量 $(N \alpha(N))$．
こちらは，merge が全部すんでから leader が来るという前提．
merge クエリを merge(a_k, b_k, l_k) として，これを，l_k の大きい順にソートする．
実際には $a_k + i$ と $b_k + i$ の merge が行われるわけだが，これを，残っている列の長い順に，
つまり，$l_k - i$ の大きい順に行う． $l_k - i$ が同じ時には，クエリをソートした順に従う．
すると，ある時点で $a_k + i$ と $b_k + i$ が merge 前にすでに同じ連結成分に属していたら， $j \geq i$ に対する $a_k + j$ と $b_k + j$ の組は見る必要が無い． $a_k + i$ と $b_k + i$ を同じ連結成分にするために必要だったそれぞれの merge(x, y) に対し， merge(x + (j - i), y + (j - i)) も実行されるからである．