标签：le NOI limits min max sum 2022 P8253 aligned

P8253 [NOI Online 2022 提高组] 如何正确地排序

Problem

有一个 \(m\times n\) 的数组 \(a_{i,j}\)。
定义： \(f(i,j)=\min\limits_{k=1}^m(a_{k,i}+a_{k,j})+\max\limits_{k=1}^m(a_{k,i}+a_{k,j})\)。

你需要求出 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^nf(i,j)\)。

\(m = 2, 3, 4\)，\(1 \le n, a_{i, j} \le 2 \times 10^{5}\)。

Solution

首先，\(m = 2, 3\) 都可以归到 \(m = 4\) 中，以下只讨论 \(m = 4\)，并记四个序列分别为 \(A, B, C, D\)。

记 \(F(T) = \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n}\min\limits_{x \in T}(x_{i} + x_{j})\)，其中 \(T\) 表示序列集合。

记 \(s_{k} = \sum\limits_{T \subseteq \{ A, B, C, D \}}F(T)\)。

利用 min-max 容斥化简答案：

\[\begin{aligned} Ans &= \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n}\left( \min\limits_{x \in \{ A, B, C, D \}}(x_{i} + x_{j}) + \max\limits_{x \in \{ A, B, C, D \}}(x_{i} + x_{j}) \right) \\ &= s_{4} + \sum\limits_{T \subseteq \{ A, B, C, D \}}(-1)^{|T| + 1}F(T) \\ &= s_{4} - s_{4} + s_{3} - s_{2} + s_{1} \\ &= s_{3} - s_{2} + s_{1} \\ \end{aligned} \]

该过程的本质是先对括号里的 \(\max\) 项进行 min-max 容斥，然后再与外层的和式组合起来。最后化简的结果是，我们把规模为 \(m = 4\) 的问题降成了规模为 \(m = 3\) 的问题。

于是我们的目标只需要求 \(s_{1}, s_{2}, s_{3}\)；更具体地，我们可以只考查 \(F(A), F(A, B), F(A, B, C)\)，然后分别枚举大小为 \(1, 2, 3\) 的的序列集合，使用相同的方法进行计算得到 \(s_{1}, s_{2}, s_{3}\)。

\(F(A)\)：

\[\begin{aligned} F(A) = \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n}(A_{i} + A_{j}) = 2n\sum\limits_{i = 1}^{n}A_{i} \\ \end{aligned} \]

\(F(A, B)\)：

考虑对以 \(A\) 作为最小值的贡献和以 \(B\) 作为最小值的贡献分别计算，并记为 \(F(A, B)|_{A}\)，\(F(A, B)|_{B}\)。这里只考虑 \(F(A, B)|_{A}\)。

由于 \(A_{i}, A_{j}\) 本质相同，所以可以只考虑 \(A_{i}\)，并将贡献 \(\times 2\)。

\[\begin{aligned} F(A, B)|_{A} &= 2\sum\limits_{i = 1}^{n}A_{i}\sum\limits_{j = 1}^{n}[A_{i} + A_{j} = \min(A_{i} + A_{j}, B_{i} + B_{j})] \\ &= 2\sum\limits_{i = 1}^{n}A_{i}\sum\limits_{j = 1}^{n}[A_{i} + A_{j} \le B_{i} + B_{j}] \\ &= 2\sum\limits_{i = 1}^{n}A_{i}\sum\limits_{j = 1}^{n}[A_{i} - B_{i} \le B_{j} - A_{j}] \\ \end{aligned} \]

直接统计即可。

\(F(A, B, C)\)：思想同上。

\[\begin{aligned} F(A, B, C)|_{A} &= 2\sum\limits_{i = 1}^{n}A_{i}\sum\limits_{j = 1}^{n}[A_{i} + A_{j} = \min(A_{i} + A_{j}, B_{i} + B_{j}, C_{i} + C_{j})] \\ &= 2\sum\limits_{i = 1}^{n}A_{i}\sum\limits_{j = 1}^{n}[A_{i} + A_{j} \le B_{i} + B_{j} \land A_{i} + A_{j} \le C_{i} + C_{j}] \\ &= 2\sum\limits_{i = 1}^{n}A_{i}\sum\limits_{j = 1}^{n}[A_{i} - B_{i} \le B_{j} - A_{j} \land A_{i} - C_{i} \le C_{j} - A_{j}] \\ \end{aligned} \]

二维偏序即可。

注意 \(A_{i} + A_{j} = B_{i} + B_{j}\) 之类的情况会计重，所以对于不同的序列求贡献时，贡献条件会有 \(\le\) 和 \(<\) 的细微差别。

标签：le,NOI,limits,min,max,sum,2022,P8253,aligned
From： https://www.cnblogs.com/Schucking-Sattin/p/17967391