https://atcoder.jp/contests/agc038/submissions/22099887
- 区間の組み合わせが線形という希望的観測をする
まず、区間[l,r]と区間[l+3,r+3]のように被っている2区間を各々ソートした結果が等しくなる条件を考えると、互いに被っていない部分にある数が動かなければ良く、被っている区間を{}で表すと小小小{中中}大大大のようになっていることだと分かる。
しかし、このままだと区間の組み合わせが から減らないので
にしたい。区間を1個ずつずらして処理できたら嬉しいという希望的観測で更に考察すると、区間[l,r]と区間[l+3,r+3]のソートした結果が同じなら区間[l+1,r+1]も区間[l+2,r+2]も同じ結果になるということに気づける（かもしれない）。よって、区間を1個ずつずらしながら前の区間とだけ比較し、被っている2区間のソートした結果が等しくなる条件を判定すれば良い。1個前の区間と比較するだけなら遅延セグ木を使って RmQ と RMQ で処理すれば
で判定できる。
つぎに、被っていない区間を各々ソートした結果が等しくなる場合もあるので考察する。この条件自体は簡単で、最初からサイズKの区間がソートされている場合となる。この条件の判定は累積和を使うと全体計算量となる。
与えられた数列に対して、最初からソートされている区間を□、1個前と同じ結果になる区間を□、で図示する。答えの最大値はN-K+1であり、□と□の数だけ減っていくことになる。当然ながら□と□が同じ区間になる場合もあり、大雑把に言えばOR演算のような処理をすれば良い。ただし、□は1個しかないときは答えを減らす必要がない上に区間数より1個だけ少ない数で減らし、□は純粋に区間数で減らすため、一度に計算せず別々にカウント処理したほうが無難と思われる。したがって、□と同じ区間の□を無視した上で N - K + 1 - (□の区間数) - max(0LL, 残った□の区間数-1) を出力する。
感想: 一度に計算しようとして頭が壊れた