Codeforces Round #371 (Div. 1) C. Sonya and Problem Wihtout A Legend
タイトルの Wihtout はタイプミス…?
http://codeforces.com/contest/713/problem/C
問題概要
数列が与えられる。要素を +1, -1 する操作ができる。数列を狭義単調増加にするのに必要な最小の操作回数を求めよ。
解法
明らかにじょうしょうツリーだったので思考停止。どうやら相当既出らしい。
n≦3000 なので DP できるが、じょうしょうツリーの解法で解いた(meldable heap は使わないけど)。
http://www.utpc.jp/2012/slides/josho.pdf
pdf の解法では中央値を heap 二個のテクで求めてるのだが、これって単なる meld ではないし O(n log n) でできるのだろうか。ならすと大丈夫なのかな。
区間 [l,r] の k 番目の値を求めるデータ構造を使えば十分なので wavelet matrix を貼った。領域木とかでも OK。
wavelet matrix のライブラリってどう作るのが使いやすいんだろう。
驚くことに持っていた wavelet matrix の構築がバグってて O(nlogn) になってなかった。