「BalticOI 2020」小丑
Analysis
问题即考虑加入一个边集，判断是否是二分图
容易想到用带权并查集/LCT 之类的结构维护
考虑对于每个左端点/右端点 维护最长的有解区间(R_i/L_i)
(L_i,R_i)显然具有单调性
就可以(O(1))完成查询
下文认为(n,m)同阶
Sol1 LCT
考虑尺取，同时用( ext{LCT})暴力维护答案合法性，下面只讲( ext{LCT})实现
考虑对于所有的边，优先加入树上，对于每一个环，只保留最后被删除的边
这样可以保证一条边被删除时，两个连通块之间没有边
同时，维护每一个连通块内的奇环边 最优集合 即可
复杂度为(O(nlog n))，速度。。。。
Sol2 分治决策单调性/整体二分
考虑用并查集维护二分图，求出(R_i)，对于(iin [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(nlog n))
由于需要维护简单的回撤操作，可以用按秩合并并查集，因此总复杂度为(O(nlog ^2n))