ARC 075 E - Meaningful Mean

• 問題
• 提出

$a'_i = a_{i+1}-K$と0-basedに直して$K$を引き、$S_k = a'_0 + a'_1 + ... + a'_{k-1}$と累積和を定めると、与えられた問題は$l < r$かつ$S_l \le S_r$であるような$(l, r) \in \{ 0, ..., N \}^2$の総数を求めることに帰着する。この数は数列$(S_k)$の転倒数$I$について$N(N+1)/2 - I$であると見ることもできるし、あるいはこれ自体を転倒数と同じように数えることもできる。

Treap、座標圧縮してBIT、マージソートの３つで通した。コンパイル時間を除くとそれぞれ250ms、100ms、60msくらいだった。BITが最速でないのを一瞬だけ意外に思ってしまったが、BITを使う前にソートするのだから単にソートするだけより遅いのは自明だった。

マージソートの高速化

マージソートで転倒数を求める時に、配列を分割していって特定のサイズ以下になったらバブルソートに切り替えるという方針が気になっていたので試してみたが、大した効果はないようだった。（長さ8以下の時にバブルソートに切り替えると3%くらいは速くなってるかも。）

→よく考えたら、挿入ソートでも転倒数を計算できるし、平均的にはそちらのほうが速いはずだ。長さ20以下のときに挿入ソートに切り替えてみたら10%くらい速くなった。

あとは再帰をやめてボトムアップにしたらどのくらい速くなるか……とか？¹ in-placeで計算する方法とかそういうのも一応は気になる。競プロで役立つことはなさそうだけど……

---

1. でも、長さ16以下で挿入ソートに切り替えれば、再帰呼び出しが9割くらい減ってる計算なのであまり意味がない気がする。 ↩︎