Educational Codeforces 65-E:Range Deleting

これが解けて紫になった。

問題

Problem - E - Codeforces

解法

　をsortした列を考える。この列を眺めていると、区間を消去できることの必要条件は

• 上で述べた列について、の値が未満のところまでは昇順である」かつ「がより大きいところからは昇順である」

が成り立つことである。をであるの最大値、をであるの最小値とする。すると、とが昇順に並ぶかどうかは、かどうかを見ればよく、容易に判定できる。
　このことをもとに、を固定したときに条件を満たすがいくつあるかを数えよう。例えばのとき、条件を満たすの値の最小値はかつを満たす最大のである。だとしてのとき、条件を満たすの値の最小値は、のとき以上であるか、存在しないかのどちらかである。これは、であることから容易にわかる。このようにして、の値を小さい順に調べ、その都度あり得るの値の最小値を尺取り法の要領で更新することで、組の個数を数えることができる。計算量はであり、十分高速である。

実装

Submission #54221712 - Codeforces

問題を見てこれは解けないといけなさそうだと思ったので、解けて嬉しかった。こどふぉのレートが上がるのは自力がついてきた実感があって良い。