https://www.luogu.org/problemnew/show/P1314
原题题意带来的坑：
1.流程三的公式是可以写成这样的：
换句话说：区间的的值=区间内满足的矿石的总个数区间内满足的矿石的价值之和
2.题干说让你输出的是在最优情况下的下的绝对值。
明确了这两个地方，我们开始分析它二分的单调性在哪里：
单调性：当你选取的检验参数越大，满足的矿石显然越少，区间的检验值就越低。
反之，当你选取的检验参数越小，满足的矿石显然会越多，区间的检验值就越大。
那么我们二分检验值，初始化二分端点,最开始时，对于任何区间，（）的值最大，()时值最小。
二分流程：
1.取变量
2.检验时所有区间的值之和：
（1）若此时,根据取值的单调性可得：下的值之和肯定时的值之和，又由于时，所以时的必然大于时的，所以时的答案不可能比时的答案更优，故取。
（2）若此时，同（1）理，时的答案不可能比时的答案更优，故取。
check函数的复杂度是的（具体维护方法见代码），所以总的时间复杂度为。
Code：
#include<cstdio>
#include<cstring>
#include<iostream>
#define ri register int
using namespace std;
const int MAXN=200020;
int n,m,w[MAXN],lft[MAXN],rit[MAXN],l,r,mid;
long long s,v[MAXN],sum[MAXN],hf[MAXN],now,ans;
//原题数据范围较大，需开long long
long long ins(long long x)
{
if(x<0) return (-1)*x;
return x;
}
long long mincmp(long long x,long long y)
{
if(x<=y) return x;
return y;
}
long long check(int minn)//二分W值
{
memset(sum,0,sizeof(sum));
memset(hf,0,sizeof(hf));
long long tot=0;
for(ri i=1;i<=n;i++)
{
sum[i]=sum[i-1],hf[i]=hf[i-1];
if(w[i]>=minn) sum[i]+=v[i],hf[i]+=1;
//hf[i]：维护区间 [1,i]内合法的矿石的个数
//sum[i]：维护区间 [1,i]内合法的矿石的价值之和。
}
for(ri i=1;i<=m;i++) tot+=(sum[rit[i]]-sum[lft[i]-1])*(hf[rit[i]]-hf[lft[i]-1]);
//利用上面O(n)维护的前缀和O(m)快速求求sigma Yi
return tot;
}
int main()
{
scanf("%d%d%lld",&n,&m,&s);
for(ri i=1;i<=n;i++)
{
scanf("%d%lld",&w[i],&v[i]);
r=max(r,w[i]);
}
for(ri i=1;i<=m;i++) scanf("%d%d",&lft[i],&rit[i]);
while(l+1<r)
{
mid=(l+r)>>1;
now=check(mid);
if(now<s) r=mid;
if(now>s) l=mid;
}
now=check(l),ans=check(r);
if(ins(now-s)<=ins(ans-s)) { cout<<ins(now-s); return 0; }//输出的时|S-Y|而非S-Y
cout<<ins(ans-s);
return 0;
}
