\from zhoumurui
题面展示
九条可怜是一个喜欢魔法的女孩子。
现在九条可怜已经学会了 n 种红魔法，第 i 种红魔法有一个法力值 a 。现在有一个 NPC，他会给九条可怜提供无数种蓝魔法，编号依次为 1,2,3,\dots ，第 i 种蓝魔法的法力值为 i 。
九条可怜每次可以选择一种红魔法和一种蓝魔法，将它们进行结合得到紫魔法紫魔法的法力值为合成它的红魔法和蓝魔法法力值的乘积。具体的，假设九条可怜选择了第 i 种红魔法和第 j 种蓝魔法，那么他得到的紫魔法的法力值为 a \times j 。每种红魔法或蓝魔法至多被用于 1 次。合成紫魔法的总法力值为所有合成的紫魔法法力值的和。
现在 NPC 给九条可怜 m 个任务，每个任务包含两个参数 p , q ，分别表示 NPC 提供的蓝魔法法力值的最大值以及九条可怜需要达到的紫魔法的总法力值下限。NPC 需要知道九条可怜最少需要使用几种红魔法，你能帮帮她吗?
1 \le n,m \le 5 \times 10^5,1 \le a_i \le 5 \times 10^5,1 \le p_i \le 10^8,1 \le q_i \le 10^{18}
解题思路
STEP 1.贪心
定理 (排序不等式) 有两个长度为 n 的递增数列 a_1,a_2,\dots,a_n 和 b_1,b_2,\dots,b_n ， j_1,j_2,\dots,j_n 为 1 ~ n 的一个排列，则：
记忆 顺序和 \ge 乱序和 \ge 倒序和。
证明 这里以左式( \sum_{i=1}^n a_i \times b_i \ge \sum_{i=1}^n a_{j_i} \times b_i)为例，右式类似:
用数学归纳法。
当 n=1 时，显然得证。
当 n=2 时，只需证明 a_1 \times b_1 + a_2 \times b_2 \ge a_1 \times b_2 + a_2 \times b_1 。
移项并因式分解得 (a_2-a_1) \times (b_2-b_1) \ge 0 。这个式子由已知条件显然正确。
假设 1 \le n \le k 时原式成立，即 \sum_{i=1}^k a_i \times b_i \ge \sum_{i=1}^k a_{j_i} \times b_i ，
那么只要证明当 n = k+1 时，原式也成立，那么就可以通过数学归纳法得证了。
用反证法。假设存在 j_1,j_2,\dots,j_n 满足 \sum_{i=1}^{k+1} a_{j_i} \times b_i \ge \sum_{i=1}^{k+1} a_i \times b_i ，
因为 a_{j_{k+1}} \times b_{j_{k+1}} + a_{k+1} \times b_{k+1} \ge a_{j_{k+1}} \times b_{k+1} + a_{k+1} \times b_{j_{k+1}} ( n=2 )
所以 \sum_{i=1}^{k+1} a_{j_i} \times b_i \le a_{j_{k+1}} \times b_{j_{k+1}} + a_{k+1} \times b_{k+1} - a_{k+1} \times b_{j_{k+1}} + \sum_{i=1}^{k} a_{j_i} \times b_i ，
由假设 \sum_{i=1}^{k+1} a_{j_i} \times b_i \ge \sum_{i=1}^{k+1} a_i \times b_i 有：
\sum_{i=1}^{k+1} a_i \times b_i \le a_{j_{k+1}} \times b_{j_{k+1}} + a_{k+1} \times b_{k+1} - a_{k+1} \times b_{j_{k+1}} ++ \sum_{i=1}^{k} a_{j_i} \times b_i
所以 \sum_{i=1}^{k} a_i \times b_i \le a_{j_{k+1}} \times b_{j_{k+1}} - a_{k+1} \times b_{j_{k+1}} + \sum_{i=1}^{k} a_{j_i} \times b_i
由归纳假设， \sum_{i=1}^k a_i \times b_i \ge \sum_{i=1}^k a_{j_i} \times b_i ，
所以 \sum_{i=1}^k a_{j_i} \times b_i \le a_{j_{k+1}} \times b_{j_{k+1}} - a_{k+1} \times b_{j_{k+1}} + \sum_{i=1}^{k} a_{j_i} \times b_i
消去一些项得 a_{j_{k+1}} \times b_{j_{k+1}} - a_{k+1} \times b_{j_{k+1}} \ge 0
显然矛盾。
由反证法和数学归纳法，知定理得证。
那么这个定理在题中的作用是什么呢？
假设我们选择了 k 个红魔法，法力值从小到大分别为 a_1,a_2,\dots,a_k ，
要和从小到大法力值分别为 b_1,b_2,\dots,b_k 的蓝魔法组合，那么最佳的组合方式是什么呢？
没错，顺序和 \ge 乱序和！
根据贪心，我们可以选择法力值最大的 k 个红魔法，与法力值最大的 k 个蓝魔法依次组合，这样得出的就是 k 个紫魔法的最大法力值！
但是对于一个 k ，计算这个答案是 O(k) 的，我们负担不起这个复杂度。
STEP 2.推公式
想让，我们首先将 a_i 从小到大排序，这样我们要选的红魔法自然是最后 k 个。
定义 \text{ans}[i] 为选择后 n-i 个红魔法，与法力值最大的 n-i 个蓝魔法依次组合的紫魔法法力值。
此时必然有 n-i \le p ，因为一共就 p 个蓝魔法，我们要选 n-i 个。
由排序不等式，
\text{ans}[k] = \sum_{i=k+1}^n (a[i] \times (p-n+i))
= \sum_{i=k+1}^n (a[i] \times(p-n)) + \sum_{i=k+1}^n (a[i] \times i)
= (p-n) \times \sum_{i=k+1}^n (a[i] ) + \sum_{i=k+1}^n (a[i] \times i)
我们想到这个问题可以用前缀和 O(1) 计算！
STEP 3.前缀和
我们只需 O(n) 预处理两个数组：
S[i]=\sum_{i=1}^n (a[i] \times i)
s[i]=\sum_{i=1}^n a[i]
这样我们就简化了公式：
\text{ans}[k]= (p-n) \times (s[n]-s[k]) + S[n]-S[k]
最后一个问题：如果枚举 k ，我们的代码依然会超时。
STEP 4.二分答案
不难注意到 \text{ans}[i] 是单调递减的(不难，请感兴趣的读者自行证明)，于是我们可以用二分答案来解决，这样就可以 O(\log n) 回答每次询问了。
核心代码展示
inline bool check(int &mid,int &p,int &q){
return (s[n]-s[mid])*(p-n)+S[n]-S[mid]>=q;
}
signed main(){
sort(a+1,a+1+n);
for (int i=1;i<=n;i++){
S[i]=S[i-1]+i*a[i];
s[i]=s[i-1]+a[i];
}
for (int i=1;i<=m;i++){
int l=max(1LL,n-p),r=n-1;
if (!check(l,p,q)){
No_Solution();
continue;
}
while (l<r){
mid=((l+r)+1)>>1;
if (check(mid,p,q))l=mid;
else r=mid-1;
}
Solution(n-l);
}
return 0;
}