計算量オーダーオタク以外お断りポテンシャルガチャコンテスト
高速道路の建設 問題概要
根付き木があります。はじめ、 $1$ 個の頂点（頂点 $1$ ）からなります。この木の各頂点は整数のパラメータを $1$ つもつ。頂点 $i$ のパラメータを $A_i$ とします。
$t=2,3,\ldots N$ の順に、次の操作を行わなければなりません。
- 頂点 $B_t$ と頂点 $t$ を辺でつなぐ。その時点で頂点 $B_t$ は木に含まれている。
- 頂点 $t$ から頂点 $1$ までの単純パス上の頂点のパラメータを並べた数列を $(a_1, a_2, a_3, \ldots , a_k)$ （ $k$ はパスの頂点数）としたとき、この数列の転倒数を求め、出力する。つまり、 $1 \leq i \lt j \leq k$ かつ $a_j \lt a_i$ を満たす組 $(i,j)$ の個数を求める。
- 頂点 $t$ から頂点 $1$ までの単純パス上のすべての頂点 $p$ について、 $A_p \leftarrow B_t$ で置き換える。
本投稿の概要
（前半）転倒数を計算する数列のランレングス圧縮を、 Sleater と Tarjan の ST-tree ( 競プロでよく使う link/cut tree ) を用いて合計の計算量 $O(N \log N)$ で求めます。
（後半）これらから実際に転倒数を求めます。要素数の合計は $O(N \log N)$ ですから計算量が $O(N (\log N)^2)$ であることが明らかですが、実は $O(N \log N \log \log N)$ になることを示します。
後半の内容は非常に複雑です。
link-cut tree を用いた高速化
LIS を求めるべき数列のランレングス圧縮を計算量 $O(N \log N)$ ですべて求めます。
解説
根を変える操作 evert を使用しない場合、 ST-tree ( a.k.a. link-cut tree ) [1] の expose は根までのパスを solid edge として他の分岐を dashed edge を用いて solid path から排除します。
高速道路の建設 の問題設定は、 link-cut tree のこの構造に非常に類似しています。頂点のパラメータを一定の値で書き換える操作は、それらをすべて solid edge でつなぐことに対応します。その結果、木の辺であって頂点のパラメータが異なるような $2$ 頂点を結ぶものは link-cut tree 上では dashed edge になります。
今回は splaying を用いるものを使います。 [2] (日本語記事は割とたくさんあるので自分で調べて)
したがって、問題設定に従って頂点を link した後 expose する際、 splice （ dashed edge と solid edge を交換する操作）のたびに記録を行うことで、ランレングス圧縮した数列を求めることができます。各ランの長さを求めるために、 link-cut tree では solid path の長さを管理します。
splice のときに構造内部の情報を取り出すこと以外は link-cut tree の操作とまったく同じですので、全体の計算量は $O(N \log N)$ です。
列挙個数のオーダー最悪のケース
十分大きい $n$ に対して、高さ $n-1$ の完全二分木を考えます。葉に dfs 順に $0,1,2, \ldots ,2^n-1$ の番号を振り、番号をビットリバーサルして得られる順番で、それぞれ頂点を $1$ つ link するとき、手順の後半では $s$ の値が毎回 $\log_2 N$ 程度になるため、列挙するものの個数が $\Theta(N \log N)$ となります。
LIS の計算全体の計算量解析
高速道路の建設 アルゴリズム後半部の計算量が $O(N \log N \log \log N)$ であることを証明します。
定数倍の差の前には誤差でしかないような気がしますが。
問題
頂点 $1$ のみからなる link-cut tree に、頂点 $2$ , $3$ , $\ldots$ , $N$ を順番に link します。ただし、 link-cut tree の根は常に頂点 $1$ にします。以下、操作 $i$ とは、頂点 $i$ を link するこの操作を指します。操作のさいに、実際の木における頂点 $i$ から頂点 $1$ までの単純パスに含まれる solid path （ $1$ 頂点のみのものも含む）の個数を $s$ として $s \log_2 s$ のコストがかかります。このときコストの総和が $O(N \log N \log \log N)$ であることを示します。
問題の変換
根までのパス上の solid path それぞれにコストを振って、全体で $s \log_2 s$ 以上になるようにします。（上から抑えるのが目的なので、勝手に大きくするのは問題ありません。）
$k$ 個目の solid path に振るべきコスト $A_k$ を考えます。 $1$ 以上の整数 $k$ について $(k+1) \log_2 (k+1)-k \log_2 k \leq \log_2 (k+1)+\sum_{t=1}^k (\log_2 (t+1)-\log_2 t) \leq 2 \log_2(k+1)$ が成り立つことから、 $A_k=2\log_2(k+1)$ （ $1 \leq k$ ）とします。
操作時に solid path に重複しないように正整数 $k$ を割り当て、 $A_k$ の総和を操作のコストとします。以下では、このコストの総和が $O(N \log N \log \log N)$ となるような正整数の割り当て方を示します。
HLD による割り当て
heavy light decomposition ( HLD ) とは、根付き木の辺を heavy path と light edge に分類することで、任意の頂点から根までのパスに含まれる light edge の個数を $\lfloor \log_2 N \rfloor$ 以下にする方法です。参考： https://qiita.com/Pro_ktmr/items/4e1e051ea0561772afa3
コストを大きく見積もるのは問題ないので、 light edge は強制的に dashed edge にして考えます。
heavy path それぞれもいくつかの solid path に分割されるため、適切に正整数を割り当てます。 heavy path は、根付き木における頂点の深さと同様に、根から数えて $0,1,2,\ldots$ と数えて何番目にあるかを考えることができます。 $h=\lfloor \log_2 N \rfloor+1$ とします。 heavy path の深さは $0$ 以上 $h$ 未満なので、深さ $d$ の heavy path に含まれる solid path に正整数 $hx-d$ ( $x$ は正整数 ) を割り当てることにすると、正整数は重複しません。
heavy path 内の構造
heavy path にパスが被るような操作を行ったとき、 heavy path 内部には dashed edge が高々 $1$ 個新しく生じます。
本来コストは dashed edge を消費した際に生じますが、 heavy path 内部では dashed edge を新しく生成した位置に応じてコストを分配します。つまり、あらかじめ各頂点に $A_{hx-d}$ ( $2 \leq x$ ) を割り当てておき、操作のパスが heavy path に入ってくる位置の頂点に割り当てたコストをその操作に押し付けます。 $2 \leq x$ としたのは、 $x=1$ の分は分割前の solid path $1$ 個の分に使用するからです。
改めて、操作の実際のコストを考えると、 heavy path を通るたびに $A_{h}$ のコスト、および進入時のコストを払いますが、それ以外のコストは以前の操作の進入時にすでに支払われてます。
二分木を用いた償却
heavy path 上の頂点を二分木のノードに対応させます。このとき、頂点の重み（部分木の大きさ）の大きい順に、根に近いほうから対応させます。
深さ $d$ のノードは $2^d$ 番目から割り当てられるので、そのノード $1$ つのの重みは全体の重みの $1/2^d$ だけしかありません。つまり、深さが $1$ 増加すると重みの上界が $1/2$ になるといえます。
また、 $A_{hx-d}$ は $x$ の小さい順に、根に近いほうから対応させます。
深さ $d$ のノードに割り当てるコストは、高々 $A_{2^{d+1}h}=2\log_2(2^{d+1}h)=2(d+1+\log_2h)$ となります。
結論を得る
HLD の heavy path をさきほどの二分木に置き換えたものを考えます。
任意の頂点から根へのパスにおいて、次が成り立ちます。
- light edge の個数は $\lfloor \log_2 N \rfloor$ 以下 ( HLD の性質 )
- heavy edge の個数は $\lfloor \log_2 N \rfloor$ 以下 ( 二分木の性質 )
また、根までのパス上の light edge の個数の最大値に $1$ を足したものを $h$ 、根までのパス上の heavy edge の個数を $D$ とすると、操作で払うべきコストは高々 $\sum 2(d+1+\log_2h) \leq 2\lbrace D+h(1+\log_2h) \rbrace$ となります。
以上より、 $1$ 回の操作で払うべきコストは $O(\log N \log \log N)$ です。
よって、 $N$ 回にわたる操作のコストの総和は $O(N \log N \log \log N)$ となります。
オーダー最悪のケース
列挙個数のオーダー最悪のケース の操作列のとき、コストの総和は $\Theta(N \log N \log \log N)$ です。
おわり
文献参照リスト
- [1] ST-tree については Daniel D. Sleator and Robert E. Tarjan. A Data Structure for Dynamic Trees から。
- [2] splaying を用いる ST-tree については Daniel D. Sleator and Robert E. Tarjan. Self-adjusting binary search trees から。