Educational Codeforces Round 152 (Rated for Div. 2)

　Dまで。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 152 (Rated for Div. 2) Dまで。
B kで割った余りでソート。
C [l,r]を[l以後にある1,r以前にある0]とし、その個数を調べる。これが意味のない区間になったときは元の配列。
D 1と2を圧縮。2が含まれていれば2にする。そして、どの0を使うかは左から貪欲。

— titia (@titia_til) July 27, 2023

E. Max to the Right of Min

　こたつがめさんの実況放送の振り返りを見てAC。

　まとめると、

・(l, r)のlを固定

・lを固定したとき、l以降の累積max、累積minを取っていれば、rから左へ見ていったとき累積maxのindexが累積minのindexより先に現れたらその(l, r)が条件を満たす。

・累積maxや累積minの差分更新はstackを使ってできる。

　あとは二分探索を使って実装した。（こたつがめさんは遅延セグ木といっていたけど、二分探索の方が自分には分かりやすかったので）

　考える方針としては、lを固定するか、最小値を固定するか、くらいしかなさそうなので、lを固定することは考えたはずなのだけど、累積maxや累積minさえ分かれば良いということにも気付いていなかった。

　それは、ちゃんと図を描いて考えましょう、くらいしか言えなそう。どういうrが条件を満たすのかよく図を見て考えるしかなさそうですね。