おかゆの競プロ(その他)日記

主に自分の解いた問題を載せていきます。競プロ以外にもなにか載せるかもしれません。

CSAcademy Round#53 C

CSAのソースコードのリンクが貼れない(わからない)ので久しぶりにブログに...

CSAcademy #Round53 - C(Histogram Partition)
N個の色んな数字からなるAという配列とN個の要素すべてが0の配列Bがあるので, Bのある区間の要素全てに1を足す, という操作をできるだけ少ない回数でAを作りなさい, という問題(答えるのはその回数).

これを, BからAにするのではなく, AからBにする.
初期区間[l, r)を[0, n)として,
1. 現在の区間の最小値を取ってくる(複数ある場合は一番左).
2. 最小値を現在の区間から引き, その最小値の位置をkとすると, [l, k)と[k+1, r)に分割し, それぞれについて1を行う.
最小値が0ならばさらにそこで分割する.
3. これをAの要素すべてが0となるまで行う.
このときの操作回数が答え.これをセグメントツリーと分割統治法でやる.
最初はStarrySky木でやろうとしたけどすんごいバグらせたのでセグメントツリーに変えた.
想定解はstackを使ってO(N)でした(すごい).