概要
問題文について
- 「’a’から’j’までのどれかの小文字のアルファベットが一つ書かれている」とありますが，正しいです．アルファベットが 10 種類であると仮定したコードで AC が可能です．
- 入力例1 の文字列には ‘l’ が含まれていますが，おかしいです．入力例1 に AC できなくとも本問題には AC します．
入力例にはクエリ 2 しかないしなかなか…．
解法
まずは巻き戻し操作を無視して解きます．
文字列は，アルファベットごとに分解すれば 01 列 10 個と見なせます．これらのローリングハッシュを求めましょう．
HLD と遅延セグメント木の利用によりパス上の文字種スワップとパス上のハッシュの取得が可能です．
これで $O(Q\sigma \log^2N)$ 時間で解けます．
実質的に [この問題] と同じなので, そちらの解説にあるような代替手段もいくつかあります．
巻き戻し操作を考慮します．
安直な方法のひとつに，遅延セグメント木を永続化するというものがありますが，時間・空間の制約を満たして AC するのは困難だと思います．
巻き戻しを含む操作列は，木構造で表せます．クエリ時点での状態を表す頂点を作り，何らかの操作をしたらその子に操作を表す頂点を追加します．巻き戻しは対応する頂点への移動です．
すると行うべきは，その木でのある頂点に居るときの 2 つのハッシュの比較です．
クエリを先読みして，同じ頂点に居るときのクエリを同時に処理できるようにしておきます．あとは，クエリ木を DFS しながらセグメント木への操作を行っていけばよいです．
DFS において辺を遡るときに遅延セグメント木の rollback 処理が必要です．一般的な遅延セグメント木の操作でこれを行うには配列の変更箇所を覚えておけばよいですが，本問では単に同じスワップをやることで rollback 可能です．
