「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