关于 U105261 「子序列删除问题」的讨论

· · 个人记录

首先，这个问题显然是一个最小割：

我们考虑将每个可以在 LIS 上的建点 u_{in} \rightarrow_1 u_{out}，其中在 LIS 中第 k 个的在第 k 层，然后给相邻层之间可以对接的连边 +\infty，我们要求的就是这样一个图的最小割。而为了找到字典序最小的那个割，我们只需从小到大访问每个点是否可以被调整。
考虑一条边是否能够存在于最小割中，我们需要通过循环流增广的调整使得 u\in S, v\in T，这需要此时的 u\rightarrow v 没有流量。我们需要将此时的 s\leadsto u\rightarrow v\leadsto t 的流量退掉。

有几个指标：V,E,A,D,L，即点数，边数，答案，图的层数，LIS 大小。

由于抽屉原理，可得 LA\le N。

接下来讨论最小割的几个做法：

一、暴力建图。

由此可知，最大流的复杂度有上界 \Theta(N^{7/3})。退流部分是 \Theta(AE) = \Theta(AN^2)，因为要判可行。

二、线段树优化建图。

由于这个图的 bfs 轮数肯定和一是相同的，因为你只是优化了中间边的 bfs 复杂度，所以最大流的复杂度有上界 \Theta(N^{5/3}\log N)。

上述分析是否正确尚不确定，但是我们还有 dinic 来源的上界 \Theta(AN^2\log^2N)

退流部分是 \Theta(AN\log N)。

三、单调队列优化建图。

这个建图的具体方法：注意到连边有如下性质：每个点对应到上一层的 L, R 各自单调。因此考虑维护一个中间点 mid，当 L > mid 时令 mid=R，暴力重构。我们有虚点 pre(mid, R) 和 suf(L, mid)，注意到 L, R 的总移动量是 \Theta(N) 的，而一次重构的点数是 \Theta(|mid - mid'|)，所以总点数和边数是 \Theta(N) 的。

由于这个图的 bfs 轮数肯定和一是相同的，因为你只是优化了中间边的 bfs 复杂度，所以最大流的复杂度有上界 \Theta(N^{5/3})。

最大流的复杂度有上界 \Theta(AN^2)。

退流部分是 \Theta(AN)。

四、不跑最大流。

首先我们将简单说明原图等价于一个平面图，这仅仅是因为各层转移的 L, R 递增。

我们考虑虚点 [L, R] 是连向 L\sim R 的每个点的，那么我们有 [L, R] \rightarrow \{[L+1,R], [L, R - 1]\}。这是一个网格图，而 [L, R] 是单调的，所以在下一个点的需要过程中，我们首先把 L 变大，这就是一个原来的直角三角形边上的一个三角形，然后扩展出来。

因此我们发现这是一个被简化的平面图，可以通过对偶最短路计算最小割。

我们记割掉 k 层第 j 个点这个拆出来的边，它下方的区域叫做 Reg(k, j)（j 是最后一个点则是 T），那么我们知道 Reg(k, j) \rightarrow Reg(k, j+1) 的代价是 1。另外，我们还可以按照反向顺序横跨 inf 边。那就是假设 (k, j) 在下一层能转移到的点在 L_j, R_j 内，我们的 Reg(k, j) 能到的点会被 Reg(k + 1, L_{j + 1}) 给 bound 住，反向类似。

这里我们跑的是一个 0/1 最短路，可以 \Theta(N) 做。

然后看看如何构造方案，我们只需每次看一条边是不是加上之后有一条最短路穿过所有被选的边。我们首先限定在最短路 DAG 上。注意可以把 0 环都缩成一个点。这个 DAG 肯定还是一个平面图，因为我们原来的 1 是 L 条链，现在是把每条链都通过一些临界边捏到一起，有些长的部分被剪掉了。然后我们只需在某层的可选边的区间被缩小的时候，递归到两边看它们两边的区间能不能被缩小，而当不缩小了我们就不往一边扩了，这个东西就可以做到 \Theta(N)。