自动搬运

查看原文

来自洛谷，原作者为

	Felix72 公式和原理永远无法推论人情。

搬运于2025-08-24 22:16:15，当前版本为作者最后更新于2025-05-12 16:02:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题大体上分为两步：

• 求出内层点可达性，转化为环上计数问题；
• DP 求解计数问题。

先对图缩点，然后尝试传递闭包。一般的闭包传递是 $O(\frac{n^2}{\omega})$ 的，但是这题的背景是平面图，因此一个点能到达的海岸线点是一个区间（去掉都不可达的海岸线点）。

于是需要我们实现一个 ModRange 类，表示在一个取模环境下的区间（即可能会有 $l > r$ 的非空区间），并且需要实现一些简单的操作，如判断相交，取并集之类的。Tarjan 之后拓扑排序求出每个点可达的海岸线点即可。

于是接着做 DP 步骤。当前问题如下：

有一个长为 $b$ 的环，有若干限制 $(l_i, r_i)$，表示一个区间内至少有一个点要选择。问合法选择方案的个数。

如果真的是上面的问题，时间复杂度这一块应该是不会小于 $O(n^2)$ 的。但是这个题比较有性质：它的 $(l_i, r_i)$ 是一条边一条边手搓出来的，也就是说它的数据大概率不强。

我们考虑通过合理连接点边，造出一组所有 $(l_i, r_i)$ 互不包含的数据。最开始所有区间都是空的，我们先加若干条边，使得每个区间非空，然后现在对于任何一组 $i, j$，$(l_i, r_i)$ 和 $(l_j, r_j)$ 不交。我们想要他们相交（这样数据变强），又不想他们互相包含，那至少得用一个额外的点（边）做这个事。我们称这个操作为加强一次数据。

这个题的数据最多加强 $O(n)$ 次，也就是说离散化之后长度最小的区间的长度不超过 $O(\frac{n}{cnt})$（$cnt$ 是区间个数）。这就意味着我们可以枚举最短的区间中最左边的被选定的点，然后断环为链 DP。一次 DP 的复杂度是 $O(cnt)$，因此在去掉包含情况且离散化后，DP 部分不成为复杂度瓶颈。

总复杂度为 $O(n\log n + m)$，因为用到了排序和离散化。