这个题很明显的二分枚举，但是还有一个前缀和有点坑人。
这题题其实点不多，就两个关键点。
二分的判断
可以看到：在W取0时，所有的区间内的矿石都可以选上，而在W大于最大的质量时，所有的矿石都选不上。
然后简单算一下就发现：W越大，矿石选的越少，W越小，矿石选的越多。
所以，随着W增大，Y值减小。
所以，二分的判断条件出来了：
当 (Y>s) 时，需要增大 (W) 来减小 (y)，从而 (|W-s|) 变小；
当 (Y=s) 时，(|Y-s|=0)；
当 (Y<s) 时，需要减小 (W) 来增大 (Y) ，从而 (|Y-s|)变大。
前缀和
我们在计算一个区间的和时（虽然这里是两个区间和再相乘，但没关系），通常是用前缀和的方法来缩减时间，直接模拟是 (n^2) 的，而前缀和成了 (2n)，大大的优化了时间。
很显然：
在 (w_i>=W) 时这个 (i) 矿石会在统计里（若 (<W) 就不管它了直接 (pre_i=pre_{i-1})），矿石价值和是：(pre_v[i]=pre_v[i-1]+v[i])，前面的和加上当前这一个 (i) 矿石；矿石数量和是：(pre_n[i]=pre_n[i-1]+1)，数量加 (1) 嘛。然后最后算的时候用右端点 (r-)（左端点 (l-1)）就可以了。
代码
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const LL N=2e5+5;
LL n,m,s,w[N],v[N],l[N],r[N],sum_n[N],sum_v[N],sum;
bool check(int W) {
LL y=0;
sum=0,memset(sum_n,0,sizeof(sum_n)),memset(sum_v,0,sizeof(sum_v));
for(int i=1; i<=n; i++) {
if(w[i]>=W) {
sum_n[i]=sum_n[i-1]+1,sum_v[i]=sum_v[i-1]+v[i];
} else {
sum_n[i]=sum_n[i-1],sum_v[i]=sum_v[i-1];
}
}
for(int i=1; i<=m; i++) {
y+=(sum_n[r[i]]-sum_n[l[i]-1])*(sum_v[r[i]]-sum_v[l[i]-1]);
}
sum=llabs(y-s);
return y>s;
}
int main() {
scanf("%lld %lld %lld",&n,&m,&s);
LL minn=LLONG_MAX>>1,maxn=0;
for(int i=1; i<=n; i++) {
scanf("%lld %lld",w+i,v+i),minn=min(minn,w[i]),maxn=max(maxn,w[i]);
}
for(int i=1; i<=m; i++) {
scanf("%lld %lld",l+i,r+i);
}
LL left=minn-1,right=maxn+1,ans=LLONG_MAX>>1;
while(left<=right) {
LL mid=(left+right)>>1;
if(check(mid)) {
left=mid+1;
} else {
right=mid-1;
}
ans=min(ans,sum);
// printf("%lld %lld %lld
",right,mid,left);//Debug
}
printf("%lld",ans);
return 0;
}
