自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 22:39:54，当前版本为作者最后更新于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)$。

代码可以私信我要。