题目链接

题意:一个没有偶环的图,问保留 [l,r] 的边的时候有多少个子区间是二分图。


二分图没奇环,原图没偶环,那么只要子区间没环就行了。

然后就太好做了,对于每个环,记其中编号最小点为 mn,最大点为 mx,显然 [mn,mx] 这个区间不能选。

所以可以给每个点处理出往右最远选到哪里,记为 nxt[i],可以写个 [1,mn] 区间更新的 seg,不过显然直接做然后后缀 min 就是线性的了。

现在考虑答案,对于 nxt[i]<=r,显然最远选到 nxt[i],这段是连续的,从某一个节点开始,最远选到 r。

二分这个位置,左边前缀和维护一下,右边直接算即可。

 


一个非常弱的准退役OIER