Codeforces#613-E:Delete a Segment

遅延セグ木で殴るのは、気持ちがいい。

問題

https://codeforces.com/contest/1285/problem/E

解法

　座標iについて、その座標を覆う区間の数をs_iとする。求めるものは、(考えるべき座標の両端のsの値が0であることにすると)s_i上で0が連続している部分(つまり区間)の数から1を引いたものになる。この値が区間を1つ取り除いたときにどうなるかを調べたい。
　ここで、遅延セグ木を用いてこの全探索を行うことを考える。各区間に持たせるべき情報を考えよう。まず、0の区間の数は当然必要である。また、区間のマージを考えると、今考えている区間の左/右端が0かどうかという情報も必要であるとわかる。さらに、区間のs_iの値を1引いたり足したりするので、sが1のときについても、0と同様の情報を持たせるべきであるとわかる。区間への作用が心配だが、今回は1か-1のどちらかで、区間を一度取り除いて戻すということしかしないため、適切に0と1の値を更新するだけでうまくいくというのがミソになる。

実装

https://codeforces.com/contest/1285/submission/68552603

セグ木力の向上を実感できてよかった。