こんなん乗せられていいはずないだろ！
っていうのがセグ木(みたいな何か)に乗るの、好きです。
解説見て、これちゃんとした名前のついてるデータ構造だったのか～と思いました。
解法
問題を見たところこれに似てるなと感じた。
B - 買い物 2 (Shopping 2)
そうなるとセグ木に乗せたいなという気になる。
どう乗せるか考えてみると、区間ごとに以下の要素の累積和が小さい計算量で求められると嬉しいので、区間ごとに
でソートされた配列の累積和を持つことにすると上手くいきそう。
これを愚直に実装するとどうなるか考える。
構築は2つの子ノードの配列を単純に結合してソートしたものを全ノード作り切ってから、改めて全ノード累積和を取ればよい。
クエリへの回答は、セグ木と同じようにボトムアップでノードをなめつつ、各ノードで二分探索によって以下の累積和を足し込めばよい。
クエリへの回答の計算量を雑に評価すると、もともとで済んでいたセグ木の操作について、各ノード
で値を取得する必要があるので、クエリごと
、全体で
となる。
構築のほうがなんかヤバそうな雰囲気になるが実は愚直のままでよい。
まず木の各段の要素数を考えると、(をちゃんとマージすると若干減るが、)どの段も常に
個になっている。これはある段でノードが
個あり、各ノード
要素持っていたとして、親の段はそれぞれのノードが
要素持つようになるが、ノードの個数が
個しかなく、段全体の要素数が変わらないことからわかる。
そして、各段の要素が1つ上の段に引き上げられるのはぞれぞれ1回ずつなので、木を構築するところまではの時間計算量で済む。
そのあと全ノードでソートが必要になるが、これは最上段のソートが最も重くなるので、結局全体ではの計算量で構築が可能。
よって、木の構築とクエリへの回答を合わせて、全体での計算量で済む。
あとがき
解説を見てみるとmerge-sort treeとか書いてあるんで改めて考えてみると、確かにこれって木のノードがマージソートする過程になっているわけですね。
つまり、木の構築の過程で各ノードをバカ真面目にソートする必要はなくて、ソート済配列のマージで済みます。木の構築の計算量がに減るのでうれしいです。
まあそんなこと知らなくてもソート済配列のマージの時点で気付けよって話なんですが、本番これ解き始めた時点で20分しか残ってなかったんで焦っていたんですよね…
致し方なしです。
