P1314 聪明的质监员
分析：
对于每一个 $Y_i$ ，有
\(Y_i = \sum\limits _{j} \times \sum\limits_jv_j , j \in [L_i, R_i] 且 w_j \geq W ，j为矿石编号\)
即区间 $[L_i ,R_i]$ 中所有 $w_j\geq W$ 的石块都选， 在区间 $[L_i ,R_i]$ 内
$Y_i = 满足条件石头个数 * 满足条件石头价值之和$
\(Y = Y_1 + Y_2 + ... + Y_i\)
即求 $abs(s - Y)$ 的最小值
考虑二分查找枚举答案 $w$
通过 $Y(w) - s$ 判断二分的区间
编写 $Y(w)$ 时，因为存在多次区间询问，考虑用前缀和降低复杂度
代码实现
#include <bits/stdc++.h>
using namespace std;
/*单调性说明:
W上升 ， 每一个 Yi 中 两项都下降， Yi下降， 所以总的 Y 也一定下降 ，单调下降（其实是不上升）
*/
int erfen(int l, int r);
long long Y (int x);
long long findnum(int l, int r);
long long findsum(int l, int r);
long long n, m, s;
long long numm[200000 + 9], summ[200000 + 9], v[200000 + 9], w[200000 + 9];//numm[] summ[] 记录区间i j 大于W的个数以及和 前缀和
int ll[200000 + 9], rr[200000 + 9];
long long read();
int main()
{
long long maxw = 0;
cin >> n >> m >> s;
for (int i = 1; i <= n; i++)
{
w[i]=read();
v[i]=read();
maxw = max(maxw, w[i]);//记录下最大重量以此为二分上边界
}
for (int i = 1; i <= m; i++)
{
ll[i] = read();
rr[i] = read();
}
int w = erfen(0, maxw);
cout << min ( Y(w) - s, s - Y(w+1) );//见下 ↓↓↓↓↓↓
return 0;
}
long long read()//快读
{
long long x=0;
char c=getchar();
while(c>'9'||c<'0')
c=getchar();
while(c<='9'&&c>='0')
{
x=x*10+c-'0';
c=getchar();
}
return x;
}
int erfen (int l, int r)//找使 Y-S >=0 的最接近的W 此时 的答案在 W与 W+1 之间 （因为要求绝对值）
{
if (l == r)
return l;
int mid = ((l+r+1)>>1);
if (Y(mid) >= s)
return erfen (mid, r);
else
return erfen (l ,mid - 1);
}
long long Y (int x)
{
long long y = 0;
for (int i = 1; i <= n; i++)//初始化
{
numm[i] = numm[i-1] ;
summ[i] = summ[i-1] ;
if(w[i] >= x) //满足条件 ，前缀和增加
{
numm[i] += 1;
summ[i] += v[i];
}
}
for (int i = 1; i <= m; i++)
{
int l = ll[i];
int r = rr[i];
y += (numm[r] - numm[l-1])* (summ[r] - summ[l-1]);
}
return y;
}
