题解：P11085 [ROI 2019] 学生座位 (Day 2)
YYH2030
·
·
题解
模拟赛考到了，未能发现可以用二分直接计算每一组的贡献和。
首先把所有被包含的区间去掉，因为显然选择包含它们的区间比选择它们自己更优。
接着假设已经确定了选择哪些桌子，考虑如何分配。
容易想到一个贪心：将所有人排序后按顺序每两个人匹配一张当前未匹配的最靠左的桌子。
具体地，假设桌子序列为 D，且满足 \forall 1\le i<n,\ L_{D_i}<L_{D_{i+1}}，当前班级所有学生的身高序列为 H，且 H 按从小到大排序，则让 H_{2i-1} 和 H_{2i} 坐 D_i 这张桌子，其中 1\le i\le n。
证明可以用调整法，具体如下。
:::info[证明]
该部分由 Deepseek 证明。
设一张桌子的适合区间为 I=[L,R]，身高 x 的不适程度为
d_I(x)=\operatorname{dist}(x,[L,R])
=
\begin{cases}
L-x,&x<L,\\
0,&L\le x\le R,\\
x-R,&x>R.
\end{cases}
删除被包含区间后，剩余类型满足
L_1<L_2<\cdots<L_K,\qquad R_1<R_2<\cdots<R_K.
因此类型 I 在类型 J 左边时，有 L_I\le L_J,\ R_I\le R_J。
若类型 I 在类型 J 左边，则函数
d_I(x)-d_J(x)
关于 x 单调不降。
这是因为 d_I(x) 和 d_J(x) 都是分段线性的凸函数，斜率只可能为 -1,0,1。由于 I 的左右端点都不大于 J 的对应端点，随着 x 增大，x 会先经过 I 的右端，再到达 J 的区间，逐段比较可得 d_I(x)-d_J(x) 的斜率始终非负，故单调不降。
于是若 a\le b，则
d_I(a)-d_J(a)\le d_I(b)-d_J(b),
即
d_I(a)+d_J(b)\le d_I(b)+d_J(a).
这说明身高较小的人坐较左边的桌子、身高较大的人坐较右边的桌子，不会比交换后更差。
因此把每个班的学生身高排序为
h_1\le h_2\le\cdots\le h_{2n},
把桌子类型按从左到右排序为 T_1,T_2,\dots,T_n，则存在最优安排使得
(h_1,h_2)\text{ 坐 }T_1,\quad
(h_3,h_4)\text{ 坐 }T_2,\quad\dots,\quad
(h_{2n-1},h_{2n})\text{ 坐 }T_n.
| 也就是说，每个班排序后相邻两人配成一对，并且所有班级的第 j 对使用同一张第 j 张桌子。 |
由于桌子可以任意摆放，且每种桌子类型购买数量不限，不同位置之间没有耦合，因此第 j 张桌子可以独立选择使总不适程度最小的类型。
设第 i 个班排序后第 2j-1 和 2j 个学生分别为 A_{i,j} 和 B_{i,j}。
再设第 j 张桌子选择类型 k 时的总成本为
F_{j,k}=\sum_{i=1}^{m}\left(\operatorname{cost}(A_{i,j},k)+\operatorname{cost}(B_{i,j},k)\right),
其中 \operatorname{cost}(x,k) 表示身高为 x 的学生选择第 k 种桌子时的不适程度。
于是答案就是：
\sum_{j=1}^{n}\min_{k}F_{j,k}.
这个东西可以做到 \mathcal{O}(nmk)，期望得分 70 pts。
考虑优化。
定义 G_j 表示使 F_{j,k} 最小的类型 k。
那么答案就是：
\sum_{j=1}^n F_{j,G_j}
再手玩一下可以发现以下性质：
\forall 1\le i<j\le n,\quad G_i\le G_j
:::info[证明]
下面证明最优类型编号关于位置单调不降。
记
d_k(x)=\operatorname{cost}(x,k).
删除被包含区间后，类型满足 L_k 和 R_k 均随 k 增大而增大。由前面的交换不等式可知，对任意 k<l 以及 x\le y，都有
d_k(x)+d_l(y)\le d_k(y)+d_l(x).
对于 j_1<j_2，由于每个班的学生身高排序后，第 j_1 对的两个身高都不超过第 j_2 对对应位置的两个身高，因此对每个班均有
d_k(A_{i,j_1})+d_l(A_{i,j_2})
\le
d_k(A_{i,j_2})+d_l(A_{i,j_1}),
以及
d_k(B_{i,j_1})+d_l(B_{i,j_2})
\le
d_k(B_{i,j_2})+d_l(B_{i,j_1}).
对 i=1,2,\dots,m 求和，得到
F_{j_1,k}+F_{j_2,l}
\le
F_{j_1,l}+F_{j_2,k}.
反设存在 j_1<j_2 但 G_{j_1}=l>k=G_{j_2}。由最优性有
F_{j_1,l}\le F_{j_1,k},\qquad
F_{j_2,k}\le F_{j_2,l}.
两式相加得
F_{j_1,l}+F_{j_2,k}
\le
F_{j_1,k}+F_{j_2,l}.
结合前面的不等式可知两边相等，即交换 j_1 和 j_2 所选的类型不会增加总成本。因此可以消除这个逆序，而不使答案变差。重复消除所有逆序，就存在一组最优选择满足
G_1\le G_2\le\cdots\le G_n.
那么这个东西就有单调性了，直接决策单调性分治可以做到 78 pts，复杂度约为 \mathcal{O}(m(n+k)\log n)（若 n,k 同阶可简写为 \mathcal{O}(mk\log n)）。
接着优化。
发现瓶颈在于给定 i 时计算 F_{i,k}。
直接遍历所有班级是 \mathcal{O}(m) 的，太慢。
可以把同一个位置 j 在所有班级中的两个身高单独提出来，设集合为 S_j，共 2m 个数，排序并做前缀和，设前缀和数组为 s。
计算 F_{j,k} 时，对桌子区间 [L_k,R_k] 分三类讨论：
- 身高小于 L_k：贡献为 p1\times L_k-s_{p1}；
- 身高大于 R_k：贡献为 (s_{2m}-s_{p2})-(2m-p2)\times R_k；
- 身高在 [L_k,R_k] 内：贡献为 0。
其中 p1 是 S_j 中小于 L_k 的数的个数，p2 是 S_j 中不大于 R_k 的数的个数，二分算一下即可，因此单次计算 F_{j,k} 只需 \mathcal{O}(\log m)。
那么总复杂度就是 \mathcal{O}\bigl(nm\log m+(n+k)\log n\log m\bigr) 可以通过。