题解 | #大风机关的忙碌#

题意：给定一段长度为n的序列A，初始状态下序列A所有位置权值均为0，但每个位置有着权值上限ai。给定m次询问，每次询问选择一段区间[l,r]，该区间上所有点的权值加k。问当进行第几次询问时会使得该序列某个位置上的权值大于权值上限？

思路：二分答案+差分维护答案正确性。首先我们可以很容易就发现答案的区间具有单调性，即如果某一次满足答案，那后面的询问肯定也满足答案，因此联想到二分答案。我们二分询问次数，然后利用差分检查该次操作而得到的答案是否合法。

细节：1.差分维护的运算过程会爆int，记得用long long；2.由于输入数据过多，cin效率不如scanf，使用cin会导致TLE出现。

AcCode：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int m,n;
ll d[1000005],need[1000005];
ll rest[1000005],di[1000005];
ll l[1000005],r[1000005];
bool chafen(int x){
	memset(di,0,sizeof(di));
	for(int i=1;i<=x;i++){
		di[l[i]]+=d[i];
		di[r[i]+1]-=d[i];
	}
	for(int i=1;i<=n;i++){
		need[i]=need[i-1]+di[i];
		if(need[i]>rest[i])return 0;
	}
	return 1;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%lld",&rest[i]);
	for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&d[i],&l[i],&r[i]);
	int begin=1,end=m;
	if(chafen(m)){
		cout<<"0";
		return 0;
	}
	int ans;
	while(begin<=end){
		int mid=(begin+end)/2;
		if(chafen(mid))begin=mid+1,ans=mid;
		else end=mid-1;
	}
	printf("%d",ans+1);
}