二分答案+前缀和+数学（某知名网站标签）

#include <bits/stdc++.h>
using namespace std;
long long n,m,s,mi=1e18;
//也可以用结构体做
vector<pair<long long,long long> > kuang;//矿石
vector<pair<long long,long long> > qu;//区间
long long qzh1[1000010];//两个前缀和数组
long long qzh2[1000010];
long long check(int x)//check函数
{
	long long y=0;//检验结果
	for (int i=1;i<=n;i++)
	{
		if (kuang[i].first>=x)//乘数
		{
			qzh1[i]=1;//第一个前缀和存表达式真假
			qzh2[i]=kuang[i].second;//第二个前缀和存矿石价值
		}
		else
		{
			qzh1[i]=0;//矿石重量>参数W为假
			qzh2[i]=0;
		}
			qzh1[i]+=qzh1[i-1];//两个前缀和预处理
			qzh2[i]+=qzh2[i-1];
	}
	for (int i=1;i<=m;i++)
	{
		y+=(qzh1[qu[i].second]-qzh1[qu[i].first-1])*(qzh2[qu[i].second]-qzh2[qu[i].first-1]);//两个前缀和计算
	}
	return y;//返回检验结果
}
int main()
{
	cin>>n>>m>>s;//输入
	kuang.push_back(make_pair(201123, 102226));//base1做，所以先传一个无用值占位
	qu.push_back(make_pair(398433,32322));
	for (int i=1;i<=n;i++)
	{
		long long momo1,momo2;
		cin>>momo1>>momo2;
		kuang.push_back(make_pair(momo1, momo2));//pair输入
	}
	for(int i=1;i<=m;i++)
	{
		long long momo1,momo2;
		cin>>momo1>>momo2;
		qu.push_back(make_pair(momo1, momo2));
	}
	long long l=1,r=1e9,ans=0;
	while(l<=r)//二分答案时间到
	{
		long long mid=(l+r)/2;
		long long y=check(mid);//二分检验结果y
		long long ans=abs(s-y);//差距
		mi=min(mi,ans);//最小值
		if (y>s)
		{
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<mi;
	return 0;
}

关于base1是因为如果按base0做的话前缀和要对0特殊处理。因为公式为a[r]-a[l-1]，会出现下标为负的情况
关于为什么用前缀和是因为我们需要O(1)地算出yi，否则会愉快的超时^_