题目
分析
本题综合考察了前缀和以及二分查找的概念。
二分法的适用性
先看检验值的计算公式。对于一个区间\([l_i, r_i]\), \(y_i=\sum_{j=l_i}^{r_i}[w_i\ge W]\times \sum_{j=l_i}^{r_i}[w_i\ge W]v_j\)。其中的\(W\)是我们“任意”选定的一个重量参数。最终，是将所有的\(y_i\)加总得到一个总的检验数值，并将其与\(W\)比较获得最小的差异。
显然，随着\(W\)的增加，一定有更少的矿石满足\(\ge W\)的条件，因此\(y_i\)的总和是递减的。在我们对\(W\)没有明确概念的前提下，我们用二分法是最好的策略。
前缀和的应用
在特定的\(W\)值下，对于一个区间，有多少矿石符合要求是确定的，我们需要两类信息对每个查询区间\([l_i, r_i]\)进行计算：
- 区间内满足条件（\(w_j >= W\)）的矿石个数\(cnt = count_{j=l}^{r} [w_j >= W]\)；
- 区间内满足条件的矿石的价值之和\(sum = \sum_{j=l}^{r} [w_j >= W] * v_j\)。
由于各个区间可能有重合，所以会有大量的重复计算。这也是使用前缀和的提示。
对于每个区间\([l, r]\)，如果对于\(i\)这个位置，我们已经计算出\([1, i-11]\)中有几个矿石满足条件（pre_sum_count[i-1]），以及总计的价值（`pre_sum_value[i-1]），那么对于\(i+1\)这个位置，有两种情形需要处理：
- 如果
i的重量大于等于目前估算的重量（\(mines[i].value\ge mid=(left+right)/2\)），那么：pre_sum_count[i]=pre_sum_count[i-1]+1; pre_sum_value[i]=pre_sum_count[i-1]+mines[i].value;。也就是数量加1，重量相应增加。 - 否则，数量和重量都不变。
到此，我们针对当前的\(mid\)值，计算了相应的前缀和。
那么针对该区间，它对最后检验值的贡献就是本区间的count*value，而这可以用上述前缀和快速计算。令R/L分别是该区间的右/左边界：
count=pre_sum_count[R]-pre_sum_count[L-1];value=pre_sum_value[R]-pre_sum_value[L-1];
答案
思考
本题的时间复杂度分析：对每个候选阈值W，我们需要\(O(n)\)的时间来构造两个前缀和（计数与价值和），并用\(O(m)\)的时间遍历所有查询区间计算检验值，因此单次判定的时间为\(O(n + m)\)。外层对阈值W进行二分（或在离散化后对不同权重值二分）需要\(O(log V)\)次判定，故总体时间复杂度为\(O((n + m) \times log V)\)，其中V为权重的取值范围或离散化后的不同权重个数。
空间复杂度为\(O(n)\)，用于存储输入数组与前缀和数组。
可选优化：若权重取值范围很大但不同权重的数量有限，可以先对所有矿石权重做离散化并在离散集合上二分，将\(log V\)降为\(log({unique\_weights})\)。在查询量极大且存在重叠区间时，也可以考虑离线或更复杂的数据结构以进一步优化整体性能。
请注意代码中，我们在求出矿石最大的重量后对其加了1。这是因为我们的二分条件（\(left\lt right\)）是不能使得mid==right的，所以加了1后，可以考虑极端的情况，也就是选中的weight==right。