2000タッチ
result:oooo--
rateing:1981->2003
■A. Reverse
a[i]!=iとなるもので一番前のものをa[j]=iとなるところまで
■B. Odd Swap Sort
手元で実験すると、奇数要素と奇数要素は前後関係が入れ替わらない。偶数も同様
なので、奇数要素と偶数要素に分け、それらがソート済みかどうか
■C. Inversion Graph
stackで頑張る。
■D. Big Brush
queueで後ろから頑張る
■E. Colorful Operations
解説を読んだ。差分の更新テクみたいな部分が勉強になった。
区間setはライブラリ化済み。
eraceとinsertを微改造するだけで使える。
insertは前後とマージできるならできるようにしていたが
本問題のようにしたら駄目なケースもある。
eraceはreturnで貰えるものを変更した区間にしておくと本問題に対応しやすくなる。
区間更新or加算、一点取得は双対セグ木で十分だが
持っていないので遅延セグ木を使う。
AtCoderならそれでもいいのだが、こどふぉでそれをやるとコード長が大変なので避けたい。
というわけで、双対セグ木をパクってACし直し。
速度半分ぐらいになるのかな？とか思いましたが意外と1/4ぐらいしか変わらず。
