洛谷P1083——差分的应用模板题

题目链接：https://www.luogu.org/problemnew/show/P1083

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n,m,r[maxn],f[maxn],a[maxn],d[maxn],***axn],t[maxn];
int judge(int mid)
{
	a[0]=0;
	memset(f,0,sizeof(a));
	for(int i=1;i<=mid;i++)
	{
		f[s[i]]+=d[i];
		f[t[i]+1]-=d[i];
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i-1]+f[i];
		if(a[i]>r[i])	return 0;
	}
	return 1;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&r[i]);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&d[i],&s[i],&t[i]);
	int mid,l=1,r=m;
	while(l<r)
	{
		mid=(l+r)/2;
		if(judge(mid))	l=mid+1;
		else r=mid;
	}
	if(m==r)	puts("0");
	else printf("-1\n%d\n",l);
	return 0;
}

一道稍微复杂一点的题目

由于在开放的oj上找不到此题所以提供样例数据：

input：

8 4 4
7 2
3 3
4 5
5 1
2 2
1 4
8 4
9 4
1 4 6 9

output:

2
3
2
2

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int an***axn],f[maxn],a[maxn],b[maxn],x[maxn];
int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
	int n,m,l;
	cin>>n>>m>>l;	
	a[0]=0;
	memset(ans,0,sizeof(an***emset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		if(b[i]>l)	continue;
		f[max(a[i]+b[i]-l,0)]++;
		f[min(a[i]+l-b[i]+1,200001)]--;
	}
	for(int i=1;i<=m;i++)
		cin>>x[i];
	ans[0]=f[0];
	for(int i=1;i<=maxn;i++)
		ans[i]=ans[i-1]+f[i];
	for(int i=1;i<=m;i++)
		cout<<ans[x[i]]<<endl;  
	return 0;
}