这题还是挺有名的，然而是个假题……原因
但是它的思维方式还是挺重要的。
思路:
我们发现一个W可以唯一确定一个y,但是W不知道。像这种情况很容易想到二分。二分可以在 (O(log n)) 的时间内多个条件 ，有时候可以先假装二分过了去想题，发现不用二分再把二分去掉。
但是再算一算，只加上二分这一个优化并不能通过极限数据（std只是在时间上过了，数据的存储并没过，这就是这题假的原因）。发现这题的瓶颈在于对于区间 ([l_i,r_i]) 我们暴力统计就已经达到 (O(n*m)) 的复杂度，做一次就已经AC不了了，考虑对这一步进行优化。弄2个前缀和数组，(sum1_i) 表示区间 [1,i]内有几个 (w_i) 比 x 大（x就是二分的那个值），(sum2_i) 表示区间[1,i]内 (w_i) 比 x 大的数的 (v_i) 的总和，于是 (O(n)) 预处理前缀数组， (O(m)) 统计即可。时间总复杂度 (O((n m)log d)) （(d=max){(w_i-w_j)}）.
code
#include<bits/stdc .h>
using namespace std;
#define int long long
const int N=200005;
const int inf=1e15;
int n,m,s,w[N],v[N],ll=inf,rr=0,ans=inf,l[N],r[N],sum1[N],sum2[N],tmp;
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
bool pd(int x)
{
memset(sum1,0,sizeof(sum1));
memset(sum2,0,sizeof(sum2));
tmp=0;
for(int i=1;i<=n; i)
if(w[i]>=x)sum1[i]=sum1[i-1] 1,sum2[i]=sum2[i-1] v[i];
else sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];
for(int i=1;i<=m; i)
tmp =(sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);
return tmp<=s;
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&s);
for(int i=1;i<=n; i)
scanf("%lld%lld",&w[i],&v[i]),ll=min(ll,w[i]),rr=max(rr,w[i]);
for(int i=1;i<=m; i)
scanf("%lld%lld",&l[i],&r[i]);
while(ll<=rr)
{
int mid=ll rr>>1;
if(pd(mid))rr=mid-1;
else ll=mid 1;
ans=min(ans,abs(tmp-s));
}
printf("%lldn",ans);
return 0;
}