题解：P5988 [PA 2019] Wyspa

Felix72 · 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)，因为用到了排序和离散化。