考察
入力は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.
出典