题解：P11847 [USACO25FEB] True or False Test P

Aegleseeker_ · 2025-10-08 16:03:00 · 题解

考虑最坏情况，主考官会尽可能的降低 Bessie 的分数，因此他会选择 a_i+b_i 最大的 k 个题。将所有题按 a_i+b_i 降序排序，则若 Bessie 选择了 c_1<c_2<\dots<c_m，最终分数为 \sum\limits_{i=k+1}^ma_i-\sum\limits_{i=1}^kb_i。由于我们对后面的 c_i 没有限制，因此肯定全选上最优，加上 a 的后缀和即可，需要最小化前面 b 的和。

一个朴素的想法是，暴力枚举 c_k 的位置，然后求前缀中 b_i 前 k 小的数的和，更新答案。前 k 小数和可以用主席树，在对应版本上主席树二分出第 k 个位置即可，这样做的复杂度是 O(qn\log n) 的。

对着单次询问做没什么优化空间了。称一次询问 k 的决策点为那个在答案出取到的位置 c_k。发现 c_k 是具有决策单调性的，即 k 增大，c_k 是不降的。因此可以直接套个决策单调性分治。复杂度 O(n\log^2n)。