二分答案

注意到当 $P$ 增大时，$Q$ 单调不上升

因此以 $P$ 作为二分时的 $mid$ ，算出 $Q$ ，以此找出第一个 $P$ 使 $Q<T$

可是题目问的是 $min |T-Q|$ 怎么办

玄学方法：对于二分求出来的 $P$ 遍历其周围的 $[P-10, P+10]$ 取 $min |T-Q|$ 即可

（不知道有没有dalao能把它hack掉）

那么如何在 $check(mid)$ 时计算出 $Q$ 呢？

对于每一个区间， $Q= \text{符合条件的零件的数量} \times \text{符合条件的W的和}$

这两个值都可以用区间前缀和计算 (talk is cheap,show me the code)

long long check(long long p){
	long long q=0;
	for (int i=1;i<=n;i++){
		cnt[i]=sum_w[i]=0;
	}
	for (int i=1;i<=n;i++){
		cnt[i]=cnt[i-1]; sum_w[i]=sum_w[i-1];
		if (v[i]>=p){
			cnt[i]+=1;
			sum_w[i]+=w[i];
		}
	}
	for (int i=1;i<=m;i++){
		q+=(cnt[b[i]]-cnt[a[i]-1])*(sum_w[b[i]]-sum_w[a[i]-1]);
	}
//	cerr<<p<<" "<<q<<endl;
	return q;
}

那么接下来就是二分了

如果你的二分难以判断何时停止？那么我强烈推荐你使用循环次数一定的二分！

long long l=1,r=2000000;
	for (int i=1;i<=30;i++){
		long long mid=(l+r)>>1;
		if (check(mid)>T){
			l=mid;
		}
		else r=mid+1;
	}

于是AC代码：

#include<iostream>
#include<cstdio>

using namespace std;

long long n,m,T,v[200005],w[200005],a[200005],b[200005],ans=1000000000000000000;

long long abbbbs(long long u){
	return u>=0?u:-u; 
}
long long cnt[200005],sum_w[200005]; 

long long check(long long p){
	long long q=0;
	for (int i=1;i<=n;i++){
		cnt[i]=sum_w[i]=0;
	}
	for (int i=1;i<=n;i++){
		cnt[i]=cnt[i-1]; sum_w[i]=sum_w[i-1];
		if (v[i]>=p){
			cnt[i]+=1;
			sum_w[i]+=w[i];
		}
	}
	for (int i=1;i<=m;i++){
		q+=(cnt[b[i]]-cnt[a[i]-1])*(sum_w[b[i]]-sum_w[a[i]-1]);
	}
//	cerr<<p<<" "<<q<<endl;
	return q;
}

int main(){
	scanf("%lld%lld%lld",&n,&m,&T);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld",v+i,w+i);
	}
	for (int i=1;i<=m;i++){
		scanf("%lld%lld",a+i,b+i);
	}
	long long l=1,r=2000000;
	for (int i=1;i<=30;i++){
		long long mid=(l+r)>>1;
		if (check(mid)>T){
			l=mid;
		}
		else r=mid+1;
	}
	for (int i=max(l-10,0ll);i<=l+10;i++){
		ans=min(ans,abbbbs(check(i)-T));
	}
	printf("%lld",ans);
	return 0;
} 

（蒟蒻的刚写好的题解被syoj吃掉了QwQ，为什么就退登了啊QwQ，我写好的题解!） 只能再写一遍了 核心思路 本题要求选择一个阈值W（后面才反应过来是p，见谅一下）使得所有查询区间内满足vi>=W的物品的「个数×权值和」之和 q 尽可能接近目标值 T。 关键性质在于单调性：当阈值 W 增大时，符合条件的物品单调不增，所以果断二分（不过我在考场上犯傻了忘了），然后最优解一定出现在从>=T变为<T的临界点附近 至于如何计算q，使用神秘的前缀和预处理加每个区间计算可以O(n+m)解决，加上二分就是O((n+m)logn)QAQ 注意事项： （本来写的很多结果被吃了，没时间了）就是不一定一定是l是最终结果，l-1,l,l+1都可能，注意一下 附上代码

#include<bits/stdc++.h>
#define lhhsyn ios::sync_with_stdio(false)
#define fc cin.tie(0)
using namespace std;
typedef long long ll;
const int N=200005;
int n,m;
ll t;
int v[N],w[N],tmp[N];
int a[N],b[N];
ll sum[N],cnt[N],q,res=1e18,l,r,mid;
void qzh(ll p){
	for(int i=1;i<=n;i++){
		cnt[i]=cnt[i-1];
		sum[i]=sum[i-1];
		if(v[i]>=p){
			cnt[i]+=1;
			sum[i]+=w[i];
		}
	}
}
ll solve(ll p){
	qzh(p);
	q=0;
	for(int j=1;j<=m;j++){
		q+=(sum[b[j]]-sum[a[j]-1])*(cnt[b[j]]-cnt[a[j]-1]);
	}
	return q;
}
int main(){
	lhhsyn;
	fc;
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>w[i];
		tmp[i]=v[i];
	}
//这何尝不是离散化
	sort(tmp+1,tmp+n+1);
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
	}
	l=1,r=n;
	while(l<r){
		mid=(l+r+1)/2;
		if(solve(tmp[mid])>=t)l=mid;
		else r=mid-1;
	}
	for(int i=l-1;i<=l+1;i++){//注意边界，我这里懒得写了，反正A了，不过这是不好的习惯，不要学
		res=min(res,abs(solve(tmp[i])-t));
	} 
	cout<<res;
	return 0;
}

做法：二分加前缀和

可以发现P与Q之间的关系具有单调性

二分找p 直接前缀和check

code:

#include <bits/stdc++.h>
using namespace std;

const long long N = 2e5 + 10;

long long n, m, t, v[N], w[N], a[N], b[N], mx;

long long s1[N], s2[N];

void read(){
	cin >> n >> m >> t;
	for(long long i = 1;i <= n; i++){
		cin >> v[i] >> w[i];
		mx = max(v[i],mx);
	}
	for(long long i = 1;i <= m; i++){
		cin >> a[i] >> b[i];
	}
	return ;
}

long long check(long long p){
	long long ans = 0;
	for(long long i = 1;i <= n; i++) {
		s1[i] = s2[i] = 0;
		if(v[i] >= p) s1[i] = 1, s2[i] = w[i];
		s1[i] += s1[i-1];
		s2[i] += s2[i-1];
	}
	for(long long i = 1;i <= m; i++){
		ans += (s1[b[i]]-s1[a[i]-1]) * (s2[b[i]]-s2[a[i]-1]);
	}
	return ans;
}

void compute(){
	long long l = 1, r = mx, ans = LLONG_MAX;
	while(l <= r){
		long long mid = (l + r) >> 1;
		long long ww = check(mid);
		if(ww >= t){
			ans = min(ans,abs(ww-t));
			l = mid + 1;
		} 
		else r = mid - 1;
	} 
	l = 1, r = mx; 
	while(l <= r){
		long long mid = (l + r) >> 1;
		long long ww = check(mid);
		if(ww <= t){
			ans = min(ans,abs(ww-t));
			r = mid - 1;
		} 
		else l = mid + 1;
	} 
	cout << ans;
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}