遅延セグ木理解したと思ったけど理解できてなかった
Union-Find。
既存の道路による接続を全てuniteしたあと、残っている根(リーダー)の個数を数える。
$K$ 個のリーダーが残っていたら、それを繋ぐために必要な道路の個数は $K-1$ 本。
セグメント木を動的に使ってのDP。
以下のDPを定義する。
すると、$i+1$ について更新したければ、$DP[i][A_{i+1}-K]~DP[i][A_{i+1}+K]$ の範囲から最大の長さを持ってきて、そこに+1すればよい。
これは、区間MAXの取得と、一点更新を行えるデータ構造があればできる。セグメント木で実装する。
$DP[i+1]$ についての更新は $DP[i]$ の情報しか不要なので、破壊的に更新していってよい。
'1
' が繋がった文字列 $S$ がある遅延伝播セグメント木。
$111111 = 100000+10000+1000+100+10+1$ と分けて、1桁ずつ管理する。
まず、セグメント木のそれぞれのノードが表す1単位を計算する。
たとえば6桁なら、こんな感じ。$S$ の初期状態でもある。
| 111111 | | 111100 | 11 | | 110000 | 1100 | 11 | 0 | |100000| 10000| 1000| 100| 10| 1| 0 | 0 |
これを $U_i$ とすると、「ノード $i$ 以下全体が $D$ に書き換えられた」=「そのノード以下全体の合計は $U_i \times D$」となる。
そして、遅延伝播セグメント木には、
というデータを乗っける。遅延データは当てはまらない場合は-1とかにしておけばいい。
そして、遅延セグ木に定義すべき演算は、以下のようになる。
適当に実装したところ上手く動かなかったので、いちから流れを確かめてバグ取りしてたら時間かかった。 どうも、「今ある値に加える」処理と「今ある値を書き換える」処理の区別が付いておらず、後者に対して実装の仕方が分かってなかった。 1)
書き換えるタイプの更新処理では上記のように、 「ノード以下が全て書き換えられるか」というフラグを持たせ、 Trueなら遅延データを参照して、Falseなら現在のデータを参照する、というのが肝要っぽい。
遅延データ側に載せるものには $mapping(a,e)=a$ を満たす単位元のような存在 $e$ が必要らしいが、これが「フラグがFalseであること」に相当するのか。なるほど。
たたみ込みを使った包除原理。
まずこのような問題は、全てのペアを作るパターン数から、当てはまらないものを除くことができるか考える。
すると、同じ身長となってしまうペアの個数で包除原理を使えそう。
まず、$2K$ 人から $K$ 個のペアを作るパターン数というのは、1個飛ばしの階乗(二重階乗)で求められる。これを最初に計算しておく。
次に、同じ身長のペアが少なくとも $k$ 個できてしまうパターン数を、$k=0,1,2,...$ で求める。
たとえば「身長10の人が7人」「身長20の人が10人」他の身長は1人ずついたとして、以下を計算していく。
すると、答えは $Pat[0]-Pat[1]+Pat[2]-Pat[3]+...$ で求められる。
問題は、$Pat$ をどう求めるか。ここにたたみ込みを用いる。
同じ身長の人が $n$ 人いたとして(これを $n$ 人グループと称する)、この中だけで、同じ身長のペアを $k$ 組作るパターン数を考える。
これは、$n$ 人の中からどの人をペアにするかで ${}_{n}C_{2k}$、その $2k$ 人をどう組み合わせるかで $Pair[k]=(2k-1)!!$、これを掛け合わせたものとなる。
たとえば7人なら、以下のようになる。
7人グループからk個のペアを作る方法 k 0 1 2 3 1 21 105 105
次に、グループが2つあったとして、その中から同じ身長のペアを合計 $k$ 組作るパターン数を考える。
たとえば7人グループと10人グループがあったとして、
10人グループからk個のペアを作る方法 k 0 1 2 3 4 5 1 45 630 3150 4725 945
「2つのグループのどちらかから、同じ身長のペアを合計 $k$ 組作るパターン数」は、たとえば $k=4$ なら以下のようになる。
7人から 10人から のペア数 のペア数 0 4 1 x 4725 = 4725 1 3 21 x 3150 = 66150 2 2 105 x 630 = 66150 3 1 105 x 45 = 4725 ----------------------- 141750
この操作は、まさにたたみ込みである。
たたみ込んだ結果は以下のようになる。
k 0 1 2 3 4 ... 8 1 66 1680 21210 141750 ... 99225
MODを取りながらのたたみ込みは、AtCoder-Libraryのconvolutionを使うと2つの配列長の和を $N$ として $O(N \log{N})$ で求めることができる。
同じ身長のグループが3個以上でも、このようなマージを順番に適用していくことで求められる。
ただし、マージにかかる計算量は、前述の通り配列の合計の長さに比例する。
適当に順番を決めてしまうと、何度も長い配列をマージすることになってしまい、TLE。
サイズの短い方から順番に行っていくと、全体で $O(N (\log{N})^2)$ になる。
「マージは小さい方から」。よく忘れて、見当違いの高速化に走りがち。
マージする順番以外は(コンテスト終了後に)自力でたどり着けたが、 正直、たたみ込みに気付いたのはAtCoder-Library Contestだからというのが大きい気がする。