题解 | #[NOIP2012]借教室#

可能是数据较弱此题可以分块过（蒟蒻不会线段树）板子题看代码即可

```#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5;
int res[maxn],s[maxn],ed[maxn],pos[maxn],mi[maxn],add[maxn];
int n,m;
bool updata(int x,int y,int d){
	int p=pos[x],q=pos[y];
	if(p==q){
		for(int i=x;i<=y;i++){
			res[i]-=d;
			if(res[i]+add[p]<0)return false;
		}
		for(int i=s[p];i<=ed[p];i++){
			mi[p]=min(mi[p],res[i]);
		}
		
	}else{
		for(int i=p+1;i<=q-1;i++){
			add[i]-=d;
			if(mi[i]+add[i]<0)return false;
		}
		for(int i=x;i<=ed[p];i++){
			res[i]-=d;
			if(res[i]+add[p]<0)return false;
		}
		for(int i=s[p];i<=ed[p];i++){
			mi[p]=min(mi[p],res[i]);
		}
		for(int i=s[q];i<=y;i++){
			res[i]-=d;
			if(res[i]+add[q]<0)return false;
		}
		for(int i=s[q];i<=ed[q];i++){
			mi[q]=min(mi[q],res[i]);
		}
	}
	return true;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	int block=sqrt(n);
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++){
		s[i]=(i-1)*block+1;
		ed[i]=i*block;
		mi[i]=INT_MAX;
	}
	ed[t]=n;
	for(int i=1;i<=n;i++){
		cin>>res[i];
		pos[i]=(i-1)/block+1;
		mi[pos[i]]=min(mi[pos[i]],res[i]);	
	}
	int ok=1;
	for(int i=1;i<=m;i++){
		int d,x,y;cin>>d>>x>>y;
		if(!updata(x,y,d)){
			cout<<-1<<'\n'<<i;
			ok=0;
			break;
		}
	}
	if(ok)cout<<0;
	return 0;
}