IOI2026 Monuments 题解

· · 题解

做了一会儿就做出来了。做不出来的鉴定为做交互去了。

我这个做法好像容易线性，不知道官方题解 log 哪来的。

把对称理解为把所有柱子分成若干组匹配，让每组和为 0。把 x,y 匹配起来的代价显然是 |x+y|。如果有两个不能动的匹配好了显然可以直接删掉，以及 0 位置所有不能动的也可以直接删掉。然后观察一下发现一组匹配只要有一个能动代价就不变。合法条件大概就是删完之后 m 不超过 n 的一半，因为要让一个能动的匹配不能动的。

然后考虑应该如何匹配。直观感受是一般都让正值匹配负值，因为如果同时有两个正值匹配，两个负值匹配，那还不如换一下。类似的，如果把 n 个数分成小的一半和大的一半，每一个匹配都会跨过分界线，左右两边匹配起来。否则就是左右两边分别有内部匹配，把原方案中移动的两个点交换目的地一定不劣。如果 n 是奇数相当于多的点必须放中间，可以加一个不能动的 0 来满足条件。

所以不妨把前半段的坐标取相反数，把代价变成 |x-y|。这样就变成了经典贪心，如果 m=0 直接排序后依次匹配即可。

相当于现在有两个点列下标为 a,b 序列，称其能不能动为 c,d 序列，c_i=0 表示能动，c_i=1 表示不能动。那第二个序列的所有 d_i=1 必须匹配第一个序列的 c_i=0。如果选出一个 c_i=0 的大小为 \sum d 的子集，那显然子集内的排序后一一匹配 d_i=1，子集外排序后一一匹配 d_i=0。这样暴力 dp 可以记 c 的前缀匹配了多少个 d_i=1，做到 O(nm)，看上去有大量的分数。

考虑最终的匹配方案中，称 i 为分界线当且仅当 \le i 的 c,d 全部都内部匹配，>i 的也全部都内部匹配。回顾一下合法条件，就是两个分界线之间能动的柱子个数大于等于不能动的柱子个数。不妨求出 s_i 为 (-1)^{c_i}+(-1)^{d_i} 的前缀和，l,r 可以是相邻分界线需要 s_r-s_l\ge 0。可以发现如果存在一个 x 满足 l<x<r,s_x-s_l\ge 0,s_r-s_x\ge 0，如果内部的匹配有跨过 x 的则一定可以调整成不跨过 x（这个只能感性理解，证明的话可以考虑对拍），所以 x 应该成为分界线。所以相邻分界线 l,r 要么满足 l+1=r（这样不可再分），要么满足 s_l=s_r 且中间的要么全 >s_l 要么全 <s_l。这样子一个 l 转移到的后继不超过 2 个（找到后面第一个 s_r=s_l）。

然后需要计算这一段区间内匹配的贡献。由于区间内 0,1 个数相同，匹配方案是唯一的。暴力计算可以做到不超过 O(n^2)。

根据对称性，只讨论计算 c_i=0 且 d_j=1 的贡献。注意这些东西一一匹配一定满足匹配 i-j 正负性相同，否则中间又可以划出来分界线。所以不妨假设 i<j。贡献系数是 |a_i-b_j|。考虑枚举一个 i，对于每个分界线左端点 l 求出它会对应哪个 j。必要条件是 l<\forall p\le i,s_p>s_l，而 s 的相邻差是 \pm2 或 0，所以所有合法的 l 的 s_l 值是公差为 2 的等差数列（即从 s_{i-1} 开始往前找，每个新的后缀最小值是合法的 s_l）。当 l=i-1 时 i 一定匹配 \ge i 的最小的 d_j=1 的 j。然后 s_l 每变小 2，匹配到的 j 会变成下一个 d_j=1 的 j（相当于前面多了一个需要匹配的 c_i=0，就只能找下一个能用的匹配）。这里 b 是单调递增的，代价是 |a_i-b_j|，所以一定是匹配到的一个前缀的 j 让 i 的贡献是 +a_i，一个后缀是 -a_i。如果用单调栈把合法的 l 的集合维护出来，相当于支持 push 和 pop，以及单调栈上区间加，求 pop 出来的数的权值，可以差分 O(1) 动态维护。弹出的时候如果弹出 s_{top}=s_{i}，则 [top,i] 是合法相邻分界线，把 top 累计的贡献记录下来即可。

根据对称性，把上面的贡献计算写八遍即可。

时间复杂度可以做到线性，但是我懒了。

代码里的注释大部分就是平方暴力，可以参考。