![問題概要
● 文字列Sがある。以下のクエリをQ個処理する。
● Sについて、文字cを文字列pで置換する。
● 部分文字列S[A..B]を出力する。
● 1 ≦ Q ≦ 3*10^5
● |S|, |p| ≦ 10
● 1 ≦ A ≦ B ≦ 10^18
● B – A ≦ 10^5](https://image.slidesharecdn.com/replace-130313021427-phpapp01/85/Replace-2-320.jpg)
Replace
- 1. replace 原案：komiya 解答：fura2, komiya スライド：komiya
- 2. 問題概要 ● 文字列Sがある。以下のクエリをQ個処理する。 ● Sについて、文字cを文字列pで置換する。 ● 部分文字列S[A..B]を出力する。 ● 1 ≦ Q ≦ 3*10^5 ● |S|, |p| ≦ 10 ● 1 ≦ A ≦ B ≦ 10^18 ● B – A ≦ 10^5
- 3. 解法(前半) ● 文字列をグラフ(DAG)っぽく持つようにする。 ● このとき、同じ文字は同じノードを表すようにし て、置換を一瞬で処理できるようにしておく。
- 4. 根 S=abaz a b z
- 5. 根 S=abaz a → cab 旧a b z c 新a
- 6. 根 S=abaz a → cab 今はどこからも参照 b → (empty) されていない 旧b z 新b c a
- 7. 根 S=abaz a → cab b → (empty) c→x z 旧c a x
- 8. 解法(後半) ● 全ての文字列をデータとして保持することは簡 単だが、その中から10^5文字出力するのは注 意しないとTLEする可能性がある。 ● グラフをメモ化探索っぽく縦断するけど、長さ0 の部分を消したり、子ノードと自ノードのサイズ が同じ時は適当に経路圧縮するように実装す ればよい。 ● スタックオーバーフローにも注意すること。
- 9. 根 (5) S=abaz サイズ0のノードへの リンクを消す a → cab b → (empty) (2) (0) z(1) （）の中はこのDAGを c→x 永続木として解釈した ときの部分木に含まれ る文字の個数 (1) a(1) x(1)
- 10. 根(5) S=abaz 出字数1のノード を圧縮する a → cab b → (empty) (2) (0) z(1) c→x (1) a(1) x(1)
- 11. 根(5) S=abaz 完成形 a → cab これでn文字分の出力が b → (empty) O(n+Q)でできる (2) z(1) c→x 理由：葉以外の出次 数が2以上なので、部 分木のサイズが葉の 個数(出力すべき文字 数)の2倍を越えない a(1) x(1)