NOI2022 D2T3

· · 题解

解法一

对于每组询问枚举每个 x_{i} 的可能取值并计算答案，复杂度

$(k - 2)$ 元组 $\left( c_{2},c_{3},\cdots,c_{k - 2} \right)$，这是由于最大化的函数的特殊性，该元组相同的所有序列中只有一个序列可能取到最优解。 # 解法二（k=3） 由于 $v_{2}$ 非负，在不影响其他元素的前提下，将序列中某个元素设为 $2

总是更优的，因为这样其在目标函数的线性项和二次项上都能获得更大的值。

故考虑处理出必须选择 1 和必须选择 3 的元素集合。此处以必须选择 1 的元素为例，3 是类似的。只有以下两种情况之一会让元素 x_{i} 必须取 1：

按照两个规则搜索或并查集求出只能选 1 的元素。

接下来将说明，对于非必须选择 1 或必须选择 3 的元素集合，它们可以同时取到 2。考察这样的序列中的所有限制：

对于值域限制而言，由于必须选择 1 和必须选择 3 的元素都被排除掉了，剩下的每个元素都必然可以取到 2；

对于元素间的限制而言，取 2 的元素两两之间限制总能得到满足；这些元素与必须取

1$ 或必须取 $3$ 的元素的取值差绝对值为 $1$。唯一不合法的情况是一个取 $2

的元素和必须取 1 或必须取 3 的元素之间有一个取值小于等于 0 的限制，但在这种情况下这个取值为 2 的元素必然分到必须选择 1 或必须选择

这样就得到了无论 $v_{2}

取值如何都固定的最优方案，根据这个方案计算每组询问对应的结果即可。复杂度

# 解法三（k=4） 考虑拓展 $k = 3$ 的做法。 **定理 1：对于任意 $k$ 和任意非负的 $\left(k - 2\right)$ 元组 $v_2,\cdots,v_{k-1}$，存在一个最优序列，非必须取 $1$ 或必须取 $k$ 的元素取到 $[2,k-1]$。** **证明：** 倘若最优方案不满足该性质，考虑将所有非必须取 $1$ 但取到 $1

的元素改为 2，非必须取 k 但取到 k 的元素改为 k - 1。与解法二中的证明类似可以证明所有限制都必然得到满足，同时目标函数取值不会变小。

应用定理 1 之后，扔掉必须取 2 或必须取 3 的元素，只需要对每个变量进行取 2 还是取 3 的抉择。

此时决策区间长度为 2，需要决策的元素两两间取值绝对值一定不超过

1$，因此它们对 $G

的贡献固定了。不考虑这部分贡献后，待决策的元素产生的贡献是线性的，即对于任意一个元素来说，选

2$ 对目标函数的影响一致，选 $3

对目标函数的影响一致。所以只有两种方案：全选择 2 或者全选择 3。

对于每组询问在这两种方案里取最大值即可。复杂度

实现中需要注意的是，必须选 $1$ 和必须选 $k

的元素可能通过变量间限制对其他元素的可取值域区间产生影响，例如必须取 1 的元素与一个取值为 [2,4] 的元素之间有一个差的绝对值不超过 2 的限制，那么 4 就不能取到。

这种取值端点的变化本质上是一个差分约束问题，可以通过最短路松弛的方式预处理：对于一个限制

$\left\lbrack l_{j},r_{j} \right\rbrack \cap \left\lbrack l_{i} - b,r_{i} + b \right\rbrack$，对 $x_{i}

类似。进行若干次直到任意一个限制不会改变值域区间后，就将元素之间限制产生的值域区间影响都考虑进去了。

在以下算法中我们认为输入数据后均运行了一次该算法。

解法三（特殊性质A）

特殊性质 A 满足没有元素之间的限制。运用定理 1之后，元素只有三种可能，可选范围分别为

$[2,4]$。 给出**命题：对于可选范围相同的元素，存在一个最优方案它们选择同一个数。** **证明：** 若存在某个可选范围，其元素选择了两种不同的值，假设分别为 $a

和 b。设 \text{va}l_{a,b} 表示将一个取值为 a 的元素变为 b 之后目标函数的改变量，则通过简单的计算可以得知

0，故将其中某个取值的一个元素改变为另一个取值更优；若两者都为 0，设定第二关键字为 $\max(a,b)$，则也存在一个改变的方法让第二关键字更优。这样不断进行调整，最终总能调整到 $\min(a,b) = 0$ 的状态。 因此只有 $2\ \times 2\ \times 3 = 12$ 种情况，每次询问计算即可，复杂度 $O(n + m + q)$。实际上情况数还可以继续优化，最少仅有5种。 # 解法四（特殊性质B） 特殊性质 B 中变量之间的限制个数不超过 10。考虑暴力枚举被任何一个变量之间的限制约束的变量的取值，这样有 $3^{2m}

种可能。但是注意到若将变量之间的限制视作边，则每个连通块之间是独立的，而且在运用定理 1 的基础上，可以将每个连通块的方案压缩成二元组

\left( c_{2},c_{4} \right)$，这是因为 $c_{2} + c_{3} + c_{4}

是一个固定的取值。这样在 O\left( 3^{m}m \right) 的复杂度下可以处理出被限制约束的所有元素取值构成的合法二元组。对于没有限制约束的元素，由特殊性质 A 的分析总共只有 12 种情况。故可以处理出 O\left( m^{2} \right) 个二元组，每次询问计算所有二元组中的最优解即可。复杂度

# 解法五（询问次数较少） 运用*定理 1*之后，可以将 $G$ 的贡献视为"每一对二元组之间一个选 $2

另一个选 4，则付出 10^{6} 的代价"。将变量之间的限制看作变量之间不满足该性质付出 + \infty 的代价，则它们均可以视作"对应二元组之间其中一个选择小于等于 v 的值、另一个选择大于等于 v + \Delta 的值后产生一定代价"，其中\Delta对于每个限制为常数。这可以使用最小割建模，建模方法可参考 HNOI2013 切糕。对于每一组询问均运行一次最大流即可。

解法六（特殊性质 C）

在数据随机时，有用的限制数较少，故猜想可以取到最优解的二元组

\left( c_{2},c_{4} \right)

的个数也较少。解法五中，运行一次最小割并计算其割集，可以得到一个可以取到最优解的

$v_{2},v_{3},v_{4}$ 的取值，得到若干 $\left( c_{2},c_{4} \right)

后去重并以这些二元组作为答案的可行范围。当运行次数在 500 左右时可以在时间限制内以很高概率得到正确结果。

解法七

上述部分分做法中不断体现一个思想：与其说我们关注序列每个元素的取值，不如说我们只关心

\left( c_{2},c_{4} \right)

这个二元组能取到哪些值，而其中哪些二元组能取到某个询问的最优解。

为考察哪些二元组可以取到某个询问的最优解，对目标函数进行简单的化简。为避免在式子中出现

n$，考察 $\left( c_{2},c_{4} \right)$ 对应的目标函数取值减去 $(0,0)

对应的目标函数取值（不管 (0,0) 是否对应一个合法方案）。相比

(0,0)$，调整 $c_{2}$ 个元素变为 $2$、$c_{4}$ 个元素变为 $4

产生的目标函数的增量为

c_{2}\left( v_{2} - v_{3} + 2 \times 10^{6}c_{1} \right) + c_{4}\left( v_{4} - v_{3} + 2 \times 10^{6}c_{5} \right) - 2 \times 10^{6}c_{2}c_{4}.

注意到这里面有 c_{2}c_{4},c_{2},c_{4} 项，故整理为

- 2 \times 10^{6}\left( c_{2} - C_{1} \right)\left( c_{4} - C_{2} \right) + C_{3},

其中 C_{1},C_{2},C_{3} 为常数。因此最小化

$\left( c_{2},c_{4} \right)$ 对应了最优解。 然后将二元组 $\left( c_{2},c_{4} \right)

嵌入到二维平面上，并考察其分布。

设 \text{min}c_{2} 为所有方案中 c_{2} 的最小值（必须选 2 的元素数），\text{max}c_{2} 为 c_{2} 的最大值，c_{4} 类似，那么有三个点

$\left\lbrack \text{min}c_{2},\text{max}c_{2} \right\rbrack \times \left\lbrack \text{min}c_{4},\text{max}c_{4} \right\rbrack

内。

求 \text{max}c_{2} 是简单的：将 \left| x_{i} - x_{j} \right| = 0 的限制对应的位置都缩在一起，每个缩在一起的部分可以选 2 就选 2 否则选

3$，这样就找到了 $\left( \text{max}c_{2},\text{min}c_{4} \right)

对应的方案。

而求 \left( c_{2} - C_{1} \right)\left( c_{4} - C_{2} \right) 的最小值则相当于将所有点集进行平移之后求横纵坐标乘积的最小值。

分类讨论平移之后

\left\lbrack \text{min}c_{2},\text{max}c_{2} \right\rbrack \times \left\lbrack \text{min}c_{4},\text{max}c_{4} \right\rbrack

的位置：

因此剩下的部分就是：找到右上方的若干个可能取到横纵坐标乘积最小值的点。

定理 2：给定第三象限上一点集，可以取到横纵坐标乘积最小值的点一定在这个点集的右上凸包上。

证明： 不妨假设点集中还有两个点

( - \infty, - \epsilon)( - \epsilon, - \infty)$，其中 $\epsilon

为足够小的常数，这两个点不影响答案。考察非右上凸包上一点

$\left( x_{1},y_{1} \right)\left( x_{2},y_{2} \right)$ 的连线，$(x,y)

一定不比这个交点优。再考虑

\left( x_{1},y_{1} \right)\left( x_{2},y_{2} \right)

确定的线段上每个点的横纵坐标乘积，这个函数关于横坐标是一个二次项系数为负的二次函数，所以一定在两端点取到最小值，所以

\left( x_{1},y_{1} \right)$ 或者 $\left( x_{2},y_{2} \right)

一定比交点优，也就比 (x,y) 优。 

因此需要找到凸包上所有的点。考虑分治：右上凸包的边界点

$\left( \text{max}c_{4},\text{min}c_{2} \right)

是已知的，而对于凸包上的两个点

$x_{1} < x_{2}$，在全体点集中找到一个点 $(x',y')$，使得 $\left( x_{1} - x_{2},y_{1} - y_{2} \right)$ 与 $(x',y')

的叉积最大，若其不在 \left( x_{1},y_{1} \right) 与

\left( x_{2},y_{2} \right)

的连线上，则其是凸包上一个新的点，将这个点分出的凸包的两段作为两个部分分治下去。

每一次分治过程中我们需要解决这样的问题：每个元素选 2 有

y_{1} - y_{2}$ 的收益，选 $4$ 有 $x_{2} - x_{1}

的收益，要求找到一个满足所有限制的方案使得收益最大。

更换一下描述，先把 y_{1} - y_{2} + x_{2} - x_{1} 的收益加上，那么选

2$ 有 $x_{2} - x_{1}$ 的代价，选 $3$ 有 $y_{1} - y_{2} + x_{2} - x_{1}

的代价，选 4 有 y_{1} - y_{2} 的代价，要求代价和最小。

把必须相等的元素缩在一起，代价乘以缩起来的元素包含的元素个数，那么有用的限制只有

\left| x_{i} - x_{j} \right| \leq 1$，意味着 $x_{i}$ 选 $2$ 时 $x_{j}

不能选 4，x_{i} 选 4 时 x_{j} 不能选 2。

以上问题也是HNOI2013切糕对应的最小割模型可以解决的问题，使用 Dinic 算法得到最小割及其割集，也就得到了在叉积意义下最优的

得到凸包上所有点之后每次询问暴力查询凸包上所有点中的最优解。复杂度看似为 $n\left( n^{2}m + q \right)$，但可以分析$\lbrack 0,n\rbrack^{2}$上整点凸包点数上界为 $O\left( n^{\frac{2}{3}} \right)$（证明细节可参考杨景钦 2017 年集训队论文），网络流图也具有良好的性质，可以分析出 $O\left( n^{2}\log n + nm \right)$ 的复杂度（证明可参考Fernández-Baca, D., & Martel, C. U. (1989). On the efficiency of maximum-flow algorithms on networks with small integer capacities. Algorithmica, 4(1-4), 173--189），故总复杂度为$O\left( n^{\frac{2}{3}}\left( n^{2}\text{log}n + nm + q \right) \right)$，结合解法一、二可以通过本题。