小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 nn 个矿石，从 11到nn逐一编号，每个矿石都有自己的重量 w_iwi 以及价值v_ivi 。检验矿产的流程是：
1 、给定mm个区间[L_i,R_i][Li,Ri]；
2 、选出一个参数WW；
3 、对于一个区间[L_i,R_i][Li,Ri]，计算矿石在这个区间上的检验值Y_iYi：
这批矿产的检验结果YY 为各个区间的检验值之和。即：Y_1+Y_2...+Y_mY1+Y2...+Ym
若这批矿产的检验结果与所给标准值SS 相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近标准值SS，即使得S-YS−Y 的绝对值最小。请你帮忙求出这个最小值。
11年的day2T2，需要一点思维和数学
首先我遇到的第一个难点是看不懂那个表达式
其实很简单，意思就是在这个区间内，重量小于W的东西的价值的和，再乘上其数量
然后我们会发现，Y的值是由W的值来决定的，随着W的增大而减小
要求的又是极值，所以自然而然的想到二分，
接下来就是如何判断了，因为是区间求和，而有时多个区间，肯定不能暴力
要用到的是前缀和优化，区间和和区间个数都能求
时间复杂度就是O（mlogw）的
别忘了开long long
下面给出代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; inline long long rd(){long long x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';return x*f; } inline void write(long long x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');return ; } long long n,m,s; long long w[1000006],v[1000006]; long long x[1000006],y[1000006]; long long sum[1000006]; long long cnt[1000006]; long long check(long long k){memset(sum,0,sizeof(sum)*2);for(long long i=1;i<=n;i++){sum[i]=sum[i-1],cnt[i]=cnt[i-1];if(w[i]>=k) sum[i]+=v[i],cnt[i]+=1;}//for(long long i=1;i<=n;i++){//cout<<sum[i]<<" ";//}long long num=0;for(long long i=1;i<=m;i++){num+=(cnt[y[i]]-cnt[x[i]-1])*(sum[y[i]]-sum[x[i]-1]);//cout<<num<<endl; }return num; } int main(){n=rd(),m=rd(),s=rd();long long l=0x7ffffffffffff,r=0;for(long long i=1;i<=n;i++){w[i]=rd(),v[i]=rd();r=max(w[i],r),l=min(l,w[i]);}for(long long i=1;i<=m;i++) x[i]=rd(),y[i]=rd();r++,l--;long long ans=0x7ffffffffffff;//write(check(4));while(l<=r){long long mid=(l+r)>>1;long long h=check(mid);if(abs(h-s)<ans) ans=abs(h-s);if(h>s) l=mid+1;else r=mid-1;}write(ans);return 0; }