https://atcoder.jp/contests/cpsco2019-s4/submissions/13597815
- 退屈Tを固定すると書き換え回数changeが計算できる
- 書き換え回数
の条件で二分探索することで退屈Tが求まる
退屈TをO(1)で考えるのは難しいので、退屈Tが許される範囲を二分探索で求める。退屈Tを固定すると（連続したN個の部分列に対して）書き換え回数はchange = N / (T+1)で簡単に計算できる。数列をランレングス圧縮で連続部分列に分解し、全ての連続部分列に対しての書き換え回数合計がK以下となる範囲を二分探索で求め、そのときの退屈Tが答えになる。計算量は
