2019-05-15
chokudai さんの で、 青色の半数が一時間でとける問題と紹介されていたもの。
累積和が使えそうなことと、まず LとRにわけて、さらにそれぞれを２つにわけるんだろうなぁというところは、 なんとなく想像がついたのだけど、そこから、方針たてられなかった。
最初の L と R を分けるのに等分するのかなぁと考えたのだけど、それについては、自分で反例を思いついてしまって、 そこで行き詰まり、解説読み。
なるほど。LとRを分ける位置について、すべて探索（O(N))、分けたあとに、それぞれまた O(N) だとダメなんだけど、 そこで、LとRを分ける位置 (i) が動くにつれて、つぎの分割 (j, k) の位置も一方向にしか動かないことを利用する。 （さらに、j, k それぞれ全探索せずに、凸であることを利用するとかかな）
解説読んで、自分で書いたのが これ。
もっと上手に書けるべきだろうし、他の人のやつ読んで勉強しないといけないんだろうけど。ひとまず今日はこれで。