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

考虑最坏情况，主考官会尽可能的降低 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)$。