この問題を(バチャ終了半年後の今日)自力ACしました。解法自体はわかっていましたが、実装に詰まって放置していました。
問題概要
配列 が与えられます。両端の連続部分列の最大値
と、真ん中の連続部分列の最小値
が一致するように、配列を三分割しなさい。
考えたこと
左端の連続部分列を固定した時に、残った部分の最適な分け方を高速に探索できると良さそう、最小値と最大値の組合せなので、配列の長さに単調性がありそう。
解法
真ん中の部分列の右端の値を とする。
が増加するにつれて
は広義単調減少する。したがって、二分探索によってこの境界を求められる。
を求める時にセグ木を用いると
でこの問題を解くことができる。
editorial は尺取り法を使っていました。僕は尺取りでやるやり方がわかりませんでした。editorial の後半の解法もかなり賢かったです。
