题解 【WR2-1E】【「Wdoi-2」禁断之门对面，是此世还是彼世】

离散小波变换° · 2022-08-15 18:52:38 · 题解

首先是进行一个柿子的推：

其中，s_i=\sum_{j=1}^i b_j。

注意到，B 矩阵是一个 n+1 行 t 列的矩阵。一共会计算 n 次贡献。每次会取出 B 矩阵的相邻两行 i 和 i+1，它们的贡献是 \varphi(B_i,B_{i+1})。其中 \varphi(a,b) 定义如下：

也就是说，假如 B_{2k+1}=P，B_{2k}=Q，其中 P,Q 为长度为 t 的值域范围 [1,m] 的每个元素互不相同且 P,Q 对应位置值不同的序列，那么总贡献就是：

从行来看，B 经历了一个 P\to Q\to P\to Q\to \cdots 的过程。可以证明，存在一种最优的方案就长成这种形状。

假设有某一种方案，形如 B_1\to B_2\to \cdots \to B_{n+1}，那么它的贡献就是 \varphi(B_1,B_2)+\varphi(B_2,B_3)+\cdots+\varphi(B_{n-1},B_n)。那么我们可以从这一大堆 \varphi 里挑出值最小的，比如 \varphi(B_k,B_{k+1})。那么我们就可以构造出这样一组方案：B_k\to B_{k+1}\to B_k\to \cdots。容易发现，这组方案不可能会更劣。令 P=B_k,Q=B_{k+1}，可以发现存在一种形如 P\to Q\to P\to Q\to \cdots 的方案是最优的。

也就是说，我们的问题转化为，找到一个 P，找到一个 Q，其中 P,Q 为长度为 t 的值域范围 [1,m] 的每个元素互不相同且 P,Q 对应位置值不同的序列，使得 \varphi (P,Q) 最小。

假如我们把 1\sim m 排成一列记作列 \alpha，视作 P 的可选元素；另外再排一列 1\sim m，视作 Q 的可选元素，记作列 \beta。我们的任务变成：

• 从 \alpha 当中选择 t 个元素，依次匹配上 \beta 内的 t 个元素，且不存在形如 (i,i) 的匹配，最小化这一组匹配的价值。一对匹配的价值的计算方式是，假定有一对匹配 (a,b)，那么这一对匹配的价值就是 S_{\max(a,b)}-S_{\min(a,b)-1}；一组匹配的价值是，它里面所有的匹配的价值之和。

如果把它转化成费用流的模型，应该长这样：

• 有一个源点 S、汇点 T、中继点 S' 和 T'。
• 点 1,2,3,\cdots m 连向了 T' 点，流量为 1，费用为 0。
• 对于 (i,j),1\le i,j\le m,i\neq j，点 i 连向了点 j'，流量为 1，费用为 S_{\max(i,j)}-S_{\min(i,j)-1}。

要求在满流的前提下最小化费用，也就是最小费用最大流。

但是直接跑费用流是会 \text{TLE} 的。注意一个重要性质：

• 存在一种最优解，对于任意 \alpha 内的点 a，它只会匹配 \beta 内的点 a-2,a-1,a+1,a+2（如果这个点存在的话）。

考虑使用调整法证明。

从左往右考虑 \alpha 和 \beta 的每个列。假定第 i 列上 \alpha_i（或者 \beta_i，其实无所谓，因为你交换 \alpha 和 \beta 就一样了）不符合要求。值得注意的是，如果 \alpha_i 不符合要求，它一定是连接到了 \beta_{i+2} 右侧的点上去（不可能是 \beta_{i-2} 左侧的点上去，否则 \beta_{i-2} 左侧的那个点就是枚举到的第一个不符合性质的点了）。

• 如果 \beta_{i+1} 或者 \beta_{i+2} 还没有被占用，那么 \alpha_i 连上那个没被占用的点，肯定是更优的。下面考虑 \beta_{i+1},\beta_{i+2} 均被占用。
• 考虑 \alpha_i 占用了 \beta_k，\alpha_{x} 占用了 \beta_{i+1}，\alpha_y 占用了 \beta_{i+2}。注意到 x,y 肯定都比 i 大。
  • 如果 x=k，那么我们可以让 \alpha_i 连上 \alpha_{i+2}，让 \alpha_{y} 连上 \beta_k。由于 y\neq x=k，于是这必定合法。
  • 如果 x\neq k，那么我们可以让 \alpha_i 连上 \alpha_{i+1}，让 \alpha_{x} 连上 \beta_k。由于 x\neq k，于是这必定合法。

为什么这样肯定不劣呢？我们本质上是交换了两组匹配。对于 i 来说，它匹配的位置向左移动了一格，代价减小；对于 i 右侧那个被匹配的点来说，它匹配的位置向右移动到了 k 的右侧，简单讨论一下就能发现总代价是减小了。

这样子有什么用呢？

考虑这样一个问题：

• 现在要从 \alpha 中选出任意个数，匹配 \beta 内的元素，使得费用和最小。比较常规的做法是，从左往右依次判断 \alpha 内每个点咋连的。也就是设 f(i) 表示考虑到前 i 个点，连接后的最小费用。

现在问题拓宽到了恰好 t 个数。怎么做呢？

考虑使用 \textbf{wqs} 二分解决本题。具体而言，我们给每个 \alpha_i 加上一个相同的额外权重 w（可能为负数），作为选择这个数来匹配带来的代价。容易发现，随着 w 的增加，那么费用最小的方案所使用的 \alpha 肯定是非严格单调递减的。记 w=x 时，费用最小的方案所使用的 \alpha 内元素的个数为 c_w。

凸性的证明：

因为该问题等价于那个费用流问题，而费用流模型的函数一定是凸的，所以这个也是凸的，可以直接套 \text{wqs} 二分。

回过头来，我们是要解决：

从 \alpha 中选出任意个数，匹配 \beta 内的元素，使得费用和最小。比较常规的做法是，从左往右依次判断 \alpha 内每个点咋连的。也就是设 f(i) 表示考虑到前 i 个点，连接后的最小费用。

由于 \alpha 内每个点只能往周围最多 2 格远连边的结论，我们只需要知道 \beta 中第 i-2,i-1,i+1,i+2 个点的占用情况，就可以进行状态压缩 dp 了。这种做法复杂度是 \mathcal O(n)，但是常数极大（因为你至少要保存 4 个状态，而转移会有 5 个方程，这些常数加一块儿就 2^4\cdot 5 了）。考虑进一步地观察优化做法。

考虑 b_i 的贡献。换言之，依次考虑 b_1,b_2,\cdots,b_m 对答案进行了多少次贡献。试证明，贡献次数忽略 0 后，只会由以下三种子段组成：

• 第一类形如 \{2,\underbrace{3,3\cdots 3}_{k\text{ 个}},2\}，这样可以处理掉 k+2 对匹配（特别地，k 可以为 0，此时退化为 \{2,2\}）；
• 第二类形如 \{1,\underbrace{2,2\cdots 2}_{k\text{ 个}},1\}，这样可以处理掉 k+1 对匹配（特别地，k 可以为 0，此时退化为 \{1,1\}）。

怎么证明呢？考虑将匹配方案划分为这样一些连续的子图（意会一下吧）：

每个子图满足如下性质：

• 子图内的 \alpha 节点和 \beta 节点一样多，且一一对应。
• 子图内每个绿色虚线线段都有线穿过。

如果一个子图内，存在 \alpha_i 和 \beta_i 的度均为 0，为了保证它是个子图，就必须出现 \alpha_{i-1}\to\beta_{i+1},\alpha_{i+1}\to\beta_{i-1} 这两条边。那么将这两条边换成 \alpha_{i-1}\to\beta_i,\alpha_{i}\to\beta_{i-1} 肯定更优。于是不会有 \alpha_i 和 \beta_i 的度均为 0。那么对于任意 i，如果 i 在这个子图的最左侧或者最右侧，那么 b_i 的贡献次数不会小于 1；如果 i 不在最左侧或者最右侧，为了使得这个图是个子图，那么 b_i 的贡献次数不会小于 2。

也就是说，对于一个子图，它里边 b_i 的贡献不严格大于 \{1,2,2,\cdots,2,1\}（这是一个偏序的关系）。对于贡献序列 \{1,2,2,\cdots,2,1\}，为了尽可能多地增加选择的边，最优的连边肯定如图所示：

这就是第一类可能的子段。

对于一个有 2t 个点的子图，如果想要选出 t 组边，只有可能是这四种情况：

这就是第二类可能的子段。

于是设计 f_i 表示，考虑 b_{1\sim i}，可以达到的尽量小的价值。g_i 表示，b_{1\sim i} 取到 f_i 时最多可以有多少个边。