聪明的质检员_(二分非边界，前缀和)

原题链接：P1314 [NOIP2011 提高组] 聪明的质监员 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 $n$ 个矿石，从 $1$ 到 $n$ 逐一编号，每个矿石都有自己的重量 $w_i$ 以及价值 $v_i$ 。检验矿产的流程是：

1. 给定$m$ 个区间 $[l_i,r_i]$；
2. 选出一个参数 $W$；
3. 对于一个区间 $[l_i,r_i]$，计算矿石在这个区间上的检验值 $y_i$：

$y_i=\sum _{j=l_i}^{r_i}[w_j\ge W]\times \sum _{j=l_i}^{r_i}[w_j\ge W]v_j$

其中 $j$ 为矿石编号。

这批矿产的检验结果 $y$ 为各个区间的检验值之和。即：$\sum _{i=1}^m{y}_i$

若这批矿产的检验结果与所给标准值 $s$ 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产，所以他想通过调整参数 $W$ 的值，让检验结果尽可能的靠近标准值 $s$，即使得 $|s-y|$ 最小。请你帮忙求出这个最小值。

思路

发现当W越大时y越小，可以二分，查找一个数满足$|s-y|$最小

但是这并不是查找某个边界，因为是绝对值，所有解可能在边界右边也可能在左边，尝试在二分时保存答案，比较后取最小值

题目给的范围比较大，每次要对一个区间查询，且查询的数值与加法有关，如果每次检查二分都要算一遍所有区间，复杂度太高，可以每次只算一次，用前缀和

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PII;
 
int n, m;
LL s;
vector<PLL> wv;
vector<PII> lr;
LL mw;
LL ans = INT64_MAX;
 
//二分减少搜索量？
LL judge(LL x)
{
    LL sumy = 0;
 
    vector<LL> w(n + 1);
    vector<LL> v(n + 1);
 
    for(int i = 1; i <= n; i ++)
    {
        if(wv[i].first >= x) w[i] = w[i - 1] + 1, v[i] = v[i - 1] + wv[i].second;
        else w[i] = w[i - 1], v[i] = v[i - 1];
    }
    for(int i = 0; i < m; i ++)
    {
        int l = lr[i].first, r = lr[i].second;
        
        sumy += (w[r] - w[l - 1]) * (v[r] - v[l - 1]);
    }
 
    return sumy;
}
 
//两个二分？
void erfen()
{
    LL l = 0, r = mw + 2;
    //因为不再是返回r，而是每次计算sum，所以当l=r时要再进入一次
    while(l <= r)
    {
        LL mid = l + r >> 1;
        LL sum = judge(mid);
        ans = min(ans, abs(s - sum));
        //越大越小，所以如果小了，就减小W,否则增加W
        if(sum < s)  r = mid - 1;
        else l = mid + 1;
    }
}
 
int main()
{
    cin >> n >> m >> s;
    wv.push_back({0, 0});
    for(int i = 0; i < n; i ++)
    {
        LL a, b;
        cin >> a >> b;
        mw = max(mw, a);
        wv.push_back({a, b});
    }
 
    for(int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> l >> r;
        lr.push_back({l, r});
    }
 
    
    erfen();
 
    cout << ans << endl;
 
    return 0;
}