原题链接
前言
这是一篇单调队列二分的题解，并补充了决策单调性的详细证明。为什么一篇单调队列二分的题解都没有呢。虽然代码没有分治好写，但是使用范围更广吧。正好题解通道还没关，写之。
思路
我们当然需要会求 \(k\) 为某一具体值时的答案。首先将 \((A_i,B_i)\) 按 \(B_i\) 升序排序，接下来说的下标都是排序后的下标。枚举 \(B_i\)，钦定它为所选 \(B\) 中最大的。接着要求出 \(A_{[1,i]}\) 中前 \(k\) 大之和作为此时的最大值。求某一前缀中前 \(k\) 大元素之和，在可持久化线段树上二分就可以。枚举 \(B_i\) 是 \(O(n)\) 的，线段树上二分是 \(O(\log V)\) 的，总复杂度 \(O(n \log V)\)。
接着我们考虑如何求出所有 \(k\) 的答案 \(ans_k\)。我们称使得 \(k\) 答案最大的 \(i\) 为 \(k\) 的决策点（最优点），记为 \(p_k\)。接下来我们证明决策是有单调性的，即
如果觉得这个可以感性理解的话，下面的证明可以跳。
设 \(f(i,k)\) 表示在前 \(i\) 个 \(A\) 中最大的 \(k\) 个 \(A_j\) 之和。再记 \(k\) 的最优点为 \(i\)，老是写 \(p_k\) 太累了喵。因为 \(i\) 是最优的，所以有
我们还有一个四边形不等式（具体解释在下面）。
不等式左边的值就是 \(A_{[1:j]}\) 中第 \(k+1\) 大的，同理右边是 \(A_{[1:i]}\) 中第 \(k+1\) 大的。\(A_{[1,i]}\) 包含了 \(A_{[1,j]}\) 中的所有数，所以第 \(k+1\) 大的值只可能更大，不可能更小。
把上面两个式子加起来，就得到了这样的式子。
这也就是说，为 \(k+1\) 选决策点时，只可能选 \(i\) 或 \(i\) 之后的点，\(i\) 之前的点绝无可能。
这样我们就证明完成了。这是所有与决策单调性有关题目的一般套路，非常值得掌握。
以上是单调队列二分与分治的共同部分，之后是单调队列二分特有的。做之前可以先做模版题 P1912 [NOI2009] 诗人小G，再做这题可以加深理解喵。那道题题解里有关单调队列二分的解释已经很好了，当然看本文的也可以。
我们发现，\(k\) 能选的决策点是所有的 \(j\ge k\)，因为小于 \(k\) 的连 \(k\) 个 \(A\) 都选不满。那我们从 \(n\) 到 \(1\) 扫一遍 \(k\)，然后依次求出答案。这样的好处是 \(k\) 能选的决策点逐渐增多，方便我们维护。
由上述决策单调性知，对于两个决策点 \(i\) 和 \(i+1\)，\(k\) 小于某一个值之前选 \(i\) 更优，跨过这个值之后选 \(i+1\) 更优。所以能将 \(i\) 作为决策点的 \(k_1\)，一定是一个区间 \([L_1,R_1]\)，而将 \(i+1\) 作为决策点的 \(k_2\)，一定是在这个区间右边，并与这个区间相临的 \([L_2,R_2]\)，其中 \(R_1 + 1 = L_2\)。换句话说，如果把 \(k\) 的决策点看作一种颜色，\(k \in [1,n]\) 就形成了一个颜色段，且决策点从左到右是逐渐增大的。
具体的，我们在双端队列里维护三元组 \((l,r,i)\)，表示此时 \(k \in [l,r]\) 的决策点是 \(i\)，保证三元组在队列里按 \(l\) 升序排列。当我们要把一个新的决策点加入队列，因为决策点是从大到小加入的，它掌管的区间的左端点一定是 \(1\)。不断找出此时优先队列中最左的区间 \((l_2,r_2,i_2)\)。计算一下，如果 \(r_2\) 选 \(i\) 作为决策点 比 \(i_2\) 更优，那 \(i_2\) 就被彻底打败了，弹出队列就可以。否则二分一个 \(mid\)，\(mid\) 以前选 \(i\) 优，\(mid\) 之后选 \(i_2\) 优，让 \(l_2=mid+1\)，再把三元组 \((1,mid,i)\) 加入就可以了。
查询简单，假设我们要查的数是 \(k\) ，查队列中最右边的组 \((l,r,i)\)，如果 \(k < l\)，那它以后也不会用到，弹掉就可以。如此我们就做完啦。
这部分的代码在下面。
int head = 1 , tail = 1;
que[1] = {1 , n , n};
go(k , n , 1){// query ans_kwhile(k < que[head].l) head++;ans[k] = cal(k , que[head].i);// insert k - 1 as a disicion pointwhile(head <= tail){if(cal(que[tail].r , que[tail].i) <= cal(que[tail].r , k - 1)) tail--; // cal(i,j) 代表 i 选 j 当决策点时的答案。else break;}if(head > tail){que[++tail] = {1 , k - 1 , k - 1};continue;}int l = que[tail].l - 1 , r = que[tail].r;while(l < r){int mid = (l + r + 1) / 2;if(cal(mid , que[tail].i) <= cal(mid , k - 1)) l = mid;else r = mid - 1;}if(l < 1) continue;que[tail].l = l + 1;tail++;que[tail] = {1 , l , k - 1};
}
fo(i , 1 , n) cout << ans[i] << "\n";
复杂度分析
显然每个 \(i\) 只会入队出队一次，是 \(O(n)\) 的，算上二分找 \(mid\) 的 \(\log n\)，以及函数 cal(i,j) 中线段树上二分的 \(\log V\)，总复杂度是和分治一样的 \(O(n \log n \log V)\)。然而实际上我的代码常数很大，在 Atcoder 上会 TLE（呜呜呜最开始还以为写挂了导致死循环）。离散化后变成 \(O(n \log^2 n)\) 过了。
下面是提交链接，可以看完整代码。
不加离散化的分治做法
不加离散化的单调队列二分做法
加离散化的单调队列二分做法
最后
当决策有单调性时，单调数据结构和分治都是常用的优化手段。关键是证明出四边形不等式，之后就只用考虑 \(w(i,j)\) 怎么维护了喵，在本题是用可持久化线段树维护。其他部分是板的。
但是分治只能处理没有依赖性的问题，而单调数据结构可以做，比如动态规划问题，也就是形如 \(f_i = \min_{j<i}f_j+w(i,j)\) 的式子。当然这也不是说分治完全没用，比如这道 CF868F Yet Another Minimization Problem。因为 \(w(i,j)\) 没有办法快速计算，只能依靠类似莫队的指针维护。