P1083 NOIP2012 借教室

本质上是区间减区间最小值。
考虑到先操作再询问，差分加前缀和即可。
对于题目要求的那个答案，我们找到第一个不合法的点，然后枚举每一个询问和它比较即可
复杂度O(n+m)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
typedef long long ll;
const int N=1000005;
ll a[N],val[N];
int qx[N],ql[N],qr[N];
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&qx[i],&ql[i],&qr[i]);
		val[ql[i]]+=qx[i],val[qr[i]+1]-=qx[i];
	}
	int loc=0;
	for(int i=1;i<=n;++i){
		val[i]+=val[i-1];
		if(val[i]>a[i]){
			loc=i;
			break;
		}
	}
	if(!loc){
		puts("0");
		return;
	}
	ll cnt=0;
	for(int i=1;i<=m;++i){
		if(ql[i]<=loc&&qr[i]>=loc){
			if(cnt+qx[i]>a[loc]){
				puts("-1");
				printf("%d\n",i);
				return;
			}else{
				cnt+=qx[i];
			}
		}
	}
}
int main(){
	init();
	return 0;
}