「BalticOI 2020」小丑

Analysis

问题即考虑加入一个边集，判断是否是二分图

容易想到用带权并查集/LCT 之类的结构维护

考虑对于每个左端点/右端点 维护最长的有解区间$R_i/L_i$

$L_i,R_i$显然具有单调性

就可以$O(1)$完成查询

下文认为$n,m$同阶

Sol1 LCT

考虑尺取，同时用$\text{LCT}$暴力维护答案合法性，下面只讲$\text{LCT}$实现

考虑对于所有的边，优先加入树上，对于每一个环，只保留最后被删除的边

这样可以保证一条边被删除时，两个连通块之间没有边

同时，维护每一个连通块内的奇环边 最优集合 即可

复杂度为$O(n\log n)$，速度。。。。

Sol2 分治决策单调性/整体二分

考虑用并查集维护二分图，求出$R_i$，对于$i\in [l,r]$，已知答案区间为$[L,R]$

通过枚举来找到$[l,r]$中答案分别为$[L,mid),[mid,R]$的两部分的界点$p$

为此我们加入$[mid+1,m]$的边，然后依次加入$[1,r]$的边，直到出现方案

直接维护复杂度显然是错的

因此考虑在分治过程中，保证分治$[l,r],[L,R]$时，$[1,l-1],[R+1,m]$的边集已经加入

此时每次操作需要移动的范围在$[l,r],[L,R]$以内

分治共$\log n$层，每层长度总和为$n$，因此移动次数为$O(n\log n)$

由于需要维护简单的回撤操作，可以用按秩合并并查集，因此总复杂度为$O(n\log ^2n)$

Loj Submission