Alea jacta est! | 题解：P8531 [Ynoi2003] 戌亥彗星

Petit_Souris · 2024-10-06 19:24:35 · 题解

放在 NOIP 模拟赛 T3 简直是再合适不过了。 什么心态。

整体思路肯定是从左到右扫描右端点，维护对应的左端点是否合法，那么查询 [l,r] 内合法的子区间数量就是查询区间的历史和。

分析一下这个海胆除了可以食用以外的性质：

首先我们需要让整个图只包含一个简单环，我们找到最靠左的 l_0，满足 [l_0,r] 只有一个环，那么一个必要条件就是 l\ge l_0。

其次需要满足整个图是联通的。由于恰好只有一个环，所以这等价于 |E|=|V|。在这条加强限制之下，l\ge l_0 已经变得充分，因为对于没有环的图都有 |E|<|V|。

考虑这件事情如何维护，显然可以双指针。动态连通性的问题想到用 LCT 维护，由于现在只有至多一个简单环了，所以我们并不需要把边拆点，维护路径最小值，不妨转而维护多出来那条边的编号，记为 c，c=0 表示没有环。如果目前断开了 (u_i,v_i) 这条边：

• 若 i=c，直接将 c 设为 0；

• 否则，若断开 (u_i,v_i) 后，u_c,v_c 不连通，则连接 (u_c,v_c)，并将 c 设为 0。

这是 LCT 板子。

最后还要满足非环点度数 \le 2，这也是具有单调性的。这可以通过维护路径上的 \deg >2 的点数来解决。判断是否合法时就查询连接环边两端的路径上的 \deg >2 的点数是否等于全局 \deg >2 的点数即可。LCT 同样支持维护可合并的路径信息，查询的时候 split 出 x\to y 这条路径，这时候这条路径对应的信息就是 LCT 上 y 子树对应的信息了。

以上就完成了维护 l_0 的过程。

接下来解决 |E|=|V| 的限制。由于 l_0 限制到的部分都满足 |E|\le |V|，所以可以直接维护 \min(|V|-|E|)，=0 的部分是合法的。那么加入边 (u_i,v_i) 的时候，要把 u_i 上一次出现的位置往后到 i 的这段区间点数 +1，v_i 同理，再对 [1,i] 的边数 -1。现在问题转化为区间加减，给一个区间打上历史最小值 +1 的 tag（保证最小值 \ge 0），查询区间历史和。可以直接用线段树维护。

时间复杂度 \mathcal O(n\log n)。

代码可以私信我要。