Luogu7843 「C.E.L.U-03」布尔

题意： 有 个布尔变量 ，给出 个限制。

限制形如 （ 为 ）（ 为 ）

一共 次询问，每次询问给出一个区间 。求最少把 划分成多少段连续的区间，使得每段里的限制都可以得到一组合法解。如果无论如何都无法得到合法解，输出 -1。

，，，时限 。

---

限制是 的形式，但因为双向连边变得十分 simple，可以转为无向图连通性问题。

问题等价于：有一个有 个点的图，编号为 。给出 组无向边 。

将 连接后若存在 联通，则称区间 是不好的。

每次询问 至少划分为多少个好的区间。

---

记 为最大的 使得区间 是好的。在 上倍增即可回答询问。

接下来只需要求 。

---

考虑如何便捷地判定图是否合法。

对于 ，当 时记 ，当 时记 ，即一对中的另一个。

• ①：维护每个联通块的点集，并启发式合并，可以做到均摊 。

  这种做法由于带有均摊，只能加，不能减和撤回，难以扩展。

• ②：将原问题转化为：点有颜色（每个对子 颜色相同），若存在某个联通块有两个颜色相同的点，则不合法。

  维护两个并查集，一个是原图的并查集，一个是颜色的并查集。加边时，若前者成功后者失败，则说明不合法。

  这成功地将判定转化为了图的连通性问题。

• ③：由于本题的特殊性，有更方便的方法。

  性质：根据（对称的）连边方式，“连通” “连通”。

  结论：在对 进行一次连边后，只需判定 是否连通。

  证明：（只证连接 的情况，另一种类似）

  假设 不连通，且此时存在新的 连通。

  说明 分别与 或者 连通。

  对于第一种情况，，由引理有 。

  因此有 ，矛盾。

---

不难发现 具有单调性，利用双指针可以将问题转化为：

• 在右侧加入一条边

• 在左侧删除一条边

• 判定是否合法

在线动态图连通性可以做，但是太麻烦，常数又大，不可取。

算法一

考虑一类奇怪的 线段树分治+双指针 的算法。

记 表示加入了边 的图。初始时 。

若已经计算完了 ，准备计算 ，考虑 的增大，若向右加入 合法，则将其加入到 中，且令 加一。

此时 在 中的“存在”区间已经确定为 ，可以用线段树分治来给 加入 ，这样就不用考虑删除了。

线段树分治配合可撤回并查集，复杂度为 。

算法二

出题人用了一类奇怪的 决策单调性分治，即 表示求 且答案必在 内。

假设我们的并查集已经含有 。只需逐个加入 即可求出 。

分为两个子问题 。

对于前一个子问题，需要继承的是 ，先将原并查集恢复到 ，再加入 ，完事后再撤回即可。

对于后一个子问题，需要继承的是 ，这个在 的基础上再加入 就好。

这其实揭示了在贡献不能删除只能撤回（回滚）时，双指针配合决策单调性分治的方法。

根据决策单调性分治的经典分析，复杂度仍然是 。