P9600

Nygglatho · 2025-06-13 20:45:50 · 个人记录

• 一棵树上有两个城市 A,B，令 x 到 y 路径上的点集合（包括端点）为 P_{x,y}，你需要对点 i 分配 c_i 使得 \sum c_i\le k，同时对于一个点 x，如果 \forall i\in P_{x,A},\operatorname{dis}(i,A)\le c_i 则获得 1 收益，\forall i\in P_{x,B},\operatorname{dis}(i,B)\le c_i 则同样获得 1 收益，求合法方案中收益最大的。
• \item 显然第 i 个点只有可能有 3 种 c_i，0,\min(\operatorname{dis}(x,A),\operatorname{dis}(x,B)),\max(\operatorname{dis}(x,A),\operatorname{dis}(x,B))，下令 \min(\operatorname{dis}(x,A),\operatorname{dis}(x,B))=a_i,\max(\operatorname{dis}(x,A),\operatorname{dis}(x,B))=b_i。
• 先把点分成这三类点：
• 可以发现如果有点 x 满足 c_x=b_x，则有 \forall i\in P_{A,B},c_i\ge a_i，且 \exists i\in P_{A,B},c_i=b_i，可以分类讨论 A，B，C 类点来证明。
• 分两种讨论，第一种是不存在 x 满足 c_x=b_x，这个直接 sort 一遍优先选距离最小的即可。不需要判断是否合法，因为先选距离更远的一定不优，如上图，如果只选择了 14，改为选 12 花费的显然更少。
• 第二种是存在 c_x=b_x，这个就先让所有 C 类点的 c_i 加到 a_i，即 a_i\gets b_i, b_i\gets \infty，然后按照 b_i 排序，排序后显然可以找到一个中间点 pos，使得 \forall i\le pos,c_i=a_i 或 c_i=b_i，且 \forall i>pos,c_i=0 或 c_i=a_i。
• 这等价于证明最优方案不存在 \nexists x,y,b_x<b_y,c_x=0,c_y=b_y，显然如果存在，让 c_x\gets b_x,c_y\gets 0，此时 x,y 对答案总贡献不改变，并且 \sum c 减少了。
• 这里也不需要判断是否合法，证明跟前面类似，先选距离更远的一定不优。
• 先拆贡献，在 pos 前面的都先对 \sum c 贡献 a_i，然后前面部分就变成了 b_i-a_i，后面部分是 a_i。以下令这部分为 s_i
• 枚举 pos，二分 mid，check \sum\limits_{s_x\le mid} s_x\le k-\sum\limits_{i\le pos} a_i。
• 把这个离散化一下然后放到权值树状数组里，求 pos 答案就像前面的二分求，复杂度 O(n\log^2 n)。