JOI2018春合宿 Construction of Highway 解説
解説
木上の始点が根に固定されたパスについて，
- パス上の頂点の値を並べたときの転倒数を求める
- パス上の頂点の値をすべてある値に更新する
という操作を繰り返し行う． すでに操作されたパスの部分パスが操作されることはない．
さて，転倒数を毎回 $O(N\log N)$ かけて求めるのは不可能なので，すべて同じ値に更新されることを利用するのだと当たりがつけられる．
木上のパス操作なので，HL分解して考えてみると，分解した各パスについて stack を持って，$[0, i]$ が $x$ に更新されたというような情報を，$i$ の降順に必要なぶんだけ持っておけばいい． いらなくなった情報は pop するようにすれば，HL分解したこともあわせて，追加と削除は償却 $O(N\log N)$ にできる． こうして stack を（ただし，初期値の格納のために deque を使った方が実装上楽である．）うまく利用すれば，転倒数を求めるのに必要な情報を，ランレングス圧縮した状態で得られる． この情報の数も，stack の削除回数に等しいので，合計で $O(N\log N)$ 個となる．
転倒数を求めるのは，BIT を使って合計 $O(N\log^2N)$ になるので，この問題が解けた． HLD の log は軽めなので，制限時間が厳しいが，通る．
