ABC 437 E — Sort Arrays

考察

入力はA_i=A_{x_i}+[y_i]という一要素追加である。全列を実体化するとchain入力で総長Θ(N²)になる。各配列のtrie終端node[i]を保持すれば、node[x_i]のラベルy_iの子を探す一操作で追加できる。同じ子があれば共有、なければ新nodeを作り、終端へiを登録する。辞書順はnodeの終端を先、子ラベル昇順のDFS順なので、全配列を展開せずO(N log N)時間・O(N)空間で全indexを並べられる。

典型の発動条件

persistent appendで構成される列は親のtrie nodeから一edgeだけ追加しprefixを共有する。trieの終端先・子ラベル昇順DFSが可変長列の辞書順に一致する。

問題固有の要素

x_i<iで親が確定済みだからnode[x_i]を直接使える。同一列の複数indexは同じ終端にまとめ入力順へ出す。

正当性

A_i=A_{x_i}+[y_i]なのでnode[x_i]のラベルy_iの子がA_iの終端である。同じ親prefixと同じyは同nodeに統合され、各入力は高々一node増やす。辞書順ではprefix自身が延長より先、異なる次要素はラベル昇順なので、終端index先・子昇順DFSが全配列の辞書順になる。同列indexは昇順で出す。

実装上の注意

node[0]=root。node[i]=getOrCreateChild(node[x_i],y_i)として登録し、各A_iの全要素を辿り直さない。再帰depth Nに備え明示stackを使い、子昇順の訪問を維持する。

復習の核

chain x_i=i−1で展開長が二次になることを確認し、親node直接参照のO(1)prefix共有を定着させる。等列はindex昇順、短prefixは延長前。

計算量と制約

時間

O(N log N)。各persistent appendを親trie nodeから一edgeで登録し、子をラベル順に走査する。

空間

O(N)。全配列を展開せずtrie nodeを共有する。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq 3\times 10^5; 0\leq x_i\lt i; 1\leq y_i\leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sort Arrays の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Trieで共有接頭辞を索引化する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: Trieによる共有接頭辞の索引

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: Trieで共有接頭辞を索引化する

      • 文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。

      この解説で扱わないこと:

      • failure linkやZ値で接頭辞と接尾辞の一致状態を更新する文字列照合。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題