解法\(1\)：线段树 - \(O((n+m)\log n)\)
比较直观的一种做法，但是可能需要卡一下输入（这里没卡也过了，但要注意输入是\(10^6\)级的，为了保险一定要加）。
#include<bits/stdc++.h>
#define lc (x<<1)
#define rc ((x<<1)|1)
#define int long long
using namespace std;
int n,m,a[1000010],minn[4000010],tag[4000010];
void update(int x){
minn[x]=min(minn[lc],minn[rc]);
}
void ch(int x,int v){
tag[x]+=v;
minn[x]+=v;
}
void pushdown(int x){
if(tag[x]){
ch(lc,tag[x]);
ch(rc,tag[x]);
tag[x]=0;
}
}
void build(int l,int r,int x){
if(l==r){
minn[x]=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,lc);
build(mid+1,r,rc);
update(x);
}
void modify(int a,int b,int v,int l,int r,int x){
pushdown(x);
if(a<=l&&r<=b){
ch(x,v);
return;
}
int mid=(l+r)>>1;
if(a<=mid) modify(a,b,v,l,mid,lc);
if(b>mid) modify(a,b,v,mid+1,r,rc);
update(x);
}
int query(int a,int b,int l,int r,int x){
pushdown(x);
if(a<=l&&r<=b) return minn[x];
int mid=(l+r)>>1,ans=LLONG_MAX;
if(a<=mid) ans=min(ans,query(a,b,l,mid,lc));
if(b>mid) ans=min(ans,query(a,b,mid+1,r,rc));
return ans;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
for(int i=1;i<=m;i++){
int v,l,r;
cin>>v>>l>>r;
modify(l,r,-v,1,n,1);
if(query(1,n,1,n,1)<0){
cout<<"-1\n"<<i<<"\n";
return 0;
}
}
cout<<"0\n";
return 0;
}
解法\(2\)：二分答案 - \(O((n+m)\log m)\)
二分枚举申请的编号，对于枚举出的编号。通过差分，计算出处理完当前编号后，每一天剩余的教室数量。如果最终结果存在负数，则r=mid，否则l=mid+1。因为我们要找的是使存在负数的最小编号。
#include<bits/stdc++.h>
#define int long long
#define N 1000010
#define M 1000010
using namespace std;
int n,m,a[N],b[N],tb[N],c[M],ld[M],rd[M];
bool check(int d){
for(int i=1;i<=n;i++) tb[i]=b[i];
for(int i=1;i<=d;i++) tb[ld[i]]-=c[i],tb[rd[i]+1]+=c[i];
for(int i=1;i<=n;i++) tb[i]+=tb[i-1];
for(int i=1;i<=n;i++) if(tb[i]<0) return 1;
return 0;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
for(int i=1;i<=m;i++) cin>>c[i]>>ld[i]>>rd[i];
int l=1,r=m;
bool flag=0;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){//不合法
flag=1;
r=mid;
}else{
l=mid+1;
}
}
if(!flag) cout<<"0\n";
else cout<<"-1\n"<<l<<"\n";
return 0;
}
解法\(3\) - \(O(n+m)\)
总体思路就是用一个指针\(j\)，初始为\(m\)。对于每一天，判断完成操作\(1\sim j\)后是否仍然合法。如果不合法了，就把\(j\)往前挪，同时撤回操作，直到该天合法为止。
最后，如果\(j=m\)，则说明所有操作都是合法的，输出0。
否则，我们需要输出导致不合法的第一个操作。而\(j\)表示的是合法的最后一个操作，输出\(j+1\)即可。
此算法的优势在于，枚举的每一天不需要从最后开始移动指针，而是从上一天的位置开始移动，大大减少了冗余操作。
注意到\(j\)是只减不增的，所以while循环一共最多执行\(m\)次。而for一共执行\(n\)次，所以复杂度是\(O(n+m)\)。
#include<bits/stdc++.h>
#define N 1000010
#define M 1000010
#define int long long
using namespace std;
int n,m,a[N],c[M],l[M],r[M];
int cf[N];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
cin>>c[i]>>l[i]>>r[i];
cf[l[i]]+=c[i],cf[r[i]+1]-=c[i];
}
int j=m,sum=0;
//sum表示完成操作1~j后，第i天一共用去多少教室
for(int i=1;i<=n;i++){
sum+=cf[i];//cf[i]表示完成操作j之后，第i天一共用去多少个教室
while(sum>a[i]){//用去的>已有的，不合法，需要撤回操作
cf[l[j]]-=c[j],cf[r[j]+1]+=c[j];
if(l[j]<=i&&i<=r[j]) sum-=c[j];
j--;
}
}
if(j==m) cout<<"0\n";
else cout<<"-1\n"<<j+1<<"\n";
return 0;
}