我感受到了memset的力量。

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到n 逐一编号，每个矿石都有自己的重量 w_i 以及价值v_i。检验矿产的流程是：

1. 给定m个区间[L_i,R_i]；
2. 选出一个参数W；
3. 对于一个区间[L_i,R_i]，计算矿石在这个区间上的检验值Y_i：
   
   这批矿产的检验结果Y为各个区间的检验值之和。即：Y_1+Y_2...+Y_m
   若这批矿产的检验结果与所给标准值S相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近标准值S，即使得S-Y的绝对值最小。请你帮忙求出这个最小值。

原题链接

Slove

一 二分

在每个区间内，只有w[]大于W的，才能被选上。
所以W减小，被选入的矿石增多，Y增加；反之Y减小。
条件：

• Y>S,增大W，减小Y，以使|Y-S|减小。
• Y<S,减小W，增大Y，以使|Y-S|减小。
• Y=S，完美。

二 前缀和

使用前缀和以减少区间修改的时间。

• w[]>=W,sum1[i]=sum1[i-1]+1,sum2[i]=sum2[i-1]+v[i],sum1表示公式中前者，sum2表示后者。
• w[]<W,sum1[i]=sum1[i-1],sum2[i]=sum2[i-1]。

Tip

1. 答案初始值一定要设的非常大。
2. 不开longlong见祖宗。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 200010
#define ll long long
using namespace std;
ll n,m,k;
ll W;
ll ans=999999999999999999,num;
ll l=1,r,mid;
ll s[N],t[N];
ll sum1[N],sum2[N];
ll w[N],v[N];
bool sl(ll cnt){
	ll num=0;
	memset(sum1,0,sizeof(sum1));
	memset(sum2,0,sizeof(sum2));
	for(ll i=1;i<=n;i++){
		if(w[i]>=cnt) 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(ll i=1;i<=m;i++){
		num+=(sum1[t[i]]-sum1[s[i]-1])*(sum2[t[i]]-sum2[s[i]-1]);
	}
	if(num>k){
		ans=min(ans,num-k);
		return false;
	}
	ans=min(ans,k-num);
	return true;
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(ll i=1;i<=n;i++) scanf("%lld%lld",&w[i],&v[i]),r=max(r,w[i]);
	for(ll i=1;i<=m;i++) scanf("%lld%lld",&s[i],&t[i]);
	r+=2;
	while(l<r){
		mid=(l+r)/2;
		if(sl(mid)) r=mid;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
}