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) になってなかった。