(2022/02/06 23:35): Randomized Binary Search Tree の実装を修正しました

解説

\(O(N^2 \log N)\) 解法を解説します。

公式解説 の DP を貰う DP の形で書き直すと、次のようになります。

\[ \mathrm{dp}[i+1][c][m]=\begin{cases} \mathrm{dp}[i][c][m] & \text{if} \; m<v_i \\ \displaystyle \sum_{x=m+1}^{N}\mathrm{dp}[i][c][x] & \text{if} \; m=v_i \\ \mathrm{dp}[i][c-1][m] & \text{if} \; m>v_i \\ \end{cases} \]

ここで、\(v\) は \(v_{p_i}=q_i\) を満たす順列です。

さて、\(\mathrm{dp}\) テーブルの後ろ \(2\) つのパラーメータだけを残した二次元配列 \(\mathrm{dp}'\) を inplace に更新することを考えます。

1. \(m<v_i\) の部分について
   更新式から分かるように、何も更新する必要はありません。
2. \(m=v_i\) の部分について
   更新式は区間和の形をしていることに注目します。各 \(\mathrm{dp}'[c]\) を Segment Tree などで管理すれば、区間和の取得は \(O(\log N)\) で可能です。\(\mathrm{dp}\) テーブルにおいて \(m=v_i\) を満たす部分は \(O(N^2)\) 個なので、このケースの全体の計算量への寄与は \(O(N^2 \log N)\) です。
3. \(m>v_i\) の部分について
   各 \(c\) に対して \(\mathrm{dp}'[c][m]\) の \(m>v_i\) の部分を切り離したあと、\(\mathrm{dp}'[c]\) の末尾に \(\mathrm{dp}'[c-1]\) から切り離した部分を連結すればよいです。各 \(\mathrm{dp}'[c]\) を split/merge 操作が可能な平衡二分探索木で管理すれば、上記の操作は \(O(\log N)\) で可能です。各 \(i,c\) の組 (このような組は \(O(N^2)\) 個あります) に対して定数回の merge/split 操作を行うので、このケースの全体の計算量への寄与は \(O(N^2 \log N)\) です。

以上より、区間和取得および merge/split 操作が可能な平衡二分探索木を用いることで全体 \(O(N^2 \log N)\) で本問題を解くことが出来ます。

区間和取得・merge/split 操作が可能な平衡二分探索木に関しては、例えば プログラミングコンテストでのデータ構造 2　～平衡二分探索木編～ などを参照してください。

実装

提出 (C++, 111 ms) : Randomized Binary Search Tree による実装です。計算量は expected \(O(N^2 \log N)\) となります。赤黒木や Splay Tree などを用いれば worst \(O(N^2 \log N)\) となります。