题解：P17241 [IOI 2026] 纪念碑 / monuments

MadSamurai · 2026-08-12 16:05:31 · 题解

最终布局关于 0 对称，可以把除去至多一座位于 0 的纪念碑以外的所有纪念碑两两配对。每一对最终分别位于 -t,t，其中 t\ge0。

固定纪念碑不能移动，所以先处理掉最显然的部分：

• 坐标为 0 的固定纪念碑本身已经对称，直接忽略；
• 坐标分别为 x,-x 的两座固定纪念碑可以直接配成一对，按数量尽量消去。

把消去后剩余的固定纪念碑染成红色，可移动纪念碑染成蓝色，数量分别记为 r,m。每座剩余红点都必须找一座不同的蓝点移动到它的对称位置，所以若 r>m，答案为 -1。

如果 r+m 为奇数，必然有一座蓝点需要移动到 0。可以在 0 处加入一个虚拟红点，它与蓝点配对的费用就是 |x|。加入后总点数为偶数，并且仍有 r\le m。

接着把点分到左右两侧。设现在共有 2h=r+m 个点。每一对中指定一个作为最终的左侧点，另一个作为右侧点。负坐标红点只能担当左侧点，正坐标红点只能担当右侧点；虚拟的 0 红点放到左侧。剩余名额由蓝点补齐。

蓝点应该如何分配？设两个蓝点初始坐标 p\le q，却把 p 分到某个右侧目标 R\ge0，把 q 分到某个左侧目标 L\le0。交换两者后，由绝对值距离的 Monge 不等式

费用不会增加。因此一定存在最优方案，使分到左侧的蓝点是所有蓝点按坐标排序后的一个前缀。

记负红点数量为 r'，左侧一共需要 h 个点，所以取最小的 h-r' 个蓝点放到左侧，其余放到右侧。把左侧原坐标取相反数并升序排列，得到

右侧原坐标直接升序排列，得到

每个元素还保留红蓝颜色。

设原来选作左侧的点坐标为 u，右侧点坐标为 v。把它们移动到 -t,t 的最小费用为

其中等号可以看成在数轴上选择中位数：最小化 |t-(-u)|+|t-v|，最优 t 位于 -u 与 v 之间。本题的左右划分保证这个区间与 [0,+\infty) 相交。

因此问题变成：将有序数组 A,B 完美匹配，匹配 A_i,B_j 的代价为 |A_i-B_j|，但红点不能和红点匹配。

下面处理这个带颜色的有序匹配。对前 i 个位置，记四种点的数量为

并定义平衡值

若区间 [i,j) 满足 D_i=D_j，则区间内红蓝总数相等。由于 A,B 两侧各有 j-i 个元素，还能进一步推出

所以这个区间可以完全使用异色边匹配：A 中红点匹配 B 中蓝点，A 中蓝点匹配 B 中红点。

同一类匹配内部一定按坐标顺序配对最优。证明仍然是 Monge 不等式：若 x\le x'、y\le y'，则

不断消去交叉边，就得到两边分别按顺序匹配。

还需要说明为什么只考虑这种平衡区间以及同位置的蓝蓝匹配就够了。

:::info[正确性证明] 有序染色匹配引理： 存在一个最优匹配，可以从左到右分成下面两类连续段：

1. 若 A_i,B_i 都是蓝点，可以把它们直接匹配，单独构成长度为 1 的一段；
2. 一段满足 D_i=D_j 的区间 [i,j)，其中只使用两类异色匹配。

证明： 画出 A 到 B 的所有匹配边。若两条边交叉，并且交换右端点后两条边仍然合法，就用 Monge 不等式将它们取消交叉，费用不会增加。最终仍可能交叉的只有下面这一对类型：一条是 A 红配 B 蓝，另一条是 A 蓝配 B 红，因为只有此时取消交叉可能制造红红边。

特别地，一条蓝蓝边和任何边交叉时都可以合法地取消交叉，所以可以找到一个最优匹配，其中蓝蓝边不和任何边交叉。若一条不被任何边跨过的边连接 A_i 和 B_j，由它左边两侧的点数必须相同可知 i=j。因此每条蓝蓝边都能写成同位置的 A_iB_i，并且把整个问题切成若干连续段。

两个相邻蓝蓝边之间不再有蓝蓝边，只剩两类异色匹配，所以该段红蓝总数相等，即段首、段尾的 D 相同。两类异色边各自都能按序匹配；如果段内某处 D 再次回到段首值，那么该处左右两类点数已经分别相等，按序匹配不会跨过这里，原段可以继续拆开。于是每个异色段都可以取到下一次 D 相等的位置。证毕。 :::

令 nxt[i] 是 i 之后第一个满足 D_{nxt[i]}=D_i 的位置。只取第一个而不是枚举后面所有相同平衡值，是因为若一个平衡区间内部再次出现相同平衡值，两类有序匹配都恰好在这里各自配完一个前缀，不会有边跨过这个分界，费用可以直接拆成两段。

于是设 dp[i] 表示处理完两边前 i 个元素的最小费用，转移只有两个：

• 若 A_i,B_i 都是蓝点，令

  dp[i+1]\gets\min(dp[i+1],dp[i]+|A_i-B_i|);

• 若 nxt[i] 存在，设 j=\mathrm{nxt}[i]，将整个 [i,j) 按异色匹配，转移到 dp[j]。

朴素计算每个平衡段的费用仍可能达到 O(N^2)，最后要解决一批特殊的绝对值和查询。

最后离线计算所有平衡段费用。以 A 中红点匹配 B 中蓝点为例。把它们各自提取成两个有序数组 u,v。一次转移要求计算

记两段下标差为

把所有查询按 d 排序扫描。对于固定的 u_i，它所匹配的是 v_{i+d}。令

也就是 v 中不大于 u_i 的元素数量。当 d<c_i-i 时有 v_{i+d}\le u_i，u_i 在绝对值展开后的系数为 +1；越过这个阈值后系数变为 -1。

同理，令

对于固定的 v_j，其系数在 d=j-\ell_j+1 处由 -1 变为 +1。

初始时在两棵树状数组中分别放入 +u_i 和 -v_j。按 d 扫描上述翻转事件，每次翻转就是一次单点修改。处理查询时，分别取两个对应区间的树状数组和，相加便是 F(l,r,k)。