看这道题的时候，题目中的借教室我们可以看作是区间修改，如果有一天不符合的话都不行，第一反应就是线段树，维护最小值，查询的时候看是否满足要求，满足的话就区间修改。以此类推，直到出现不满足的情况。
但是由于常数问题还是要O2优化才能过，不然只有95分。
代码如下：
#include<cstdio> using namespace std; const int maxn=1e6+7; struct node{ int l,r,lazy; int mi; }tree[maxn*4]; int n,m; int val[maxn]; int d,s,t; int ask; int re; int no; bool flag; int min(int x,int y){ return x<y?x:y; } void build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r){ tree[now].mi=val[l]; return; } int mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); tree[now].mi=min(tree[now<<1].mi,tree[now<<1|1].mi); } void pushdown(int now){ if(tree[now].lazy){ tree[now<<1].mi+=tree[now].lazy; tree[now<<1|1].mi+=tree[now].lazy; tree[now<<1].lazy+=tree[now].lazy; tree[now<<1|1].lazy+=tree[now].lazy; tree[now].lazy=0; } } void update(int now,int l,int r,int v){ if(tree[now].l>=l&&tree[now].r<=r){ tree[now].lazy+=v; tree[now].mi+=v; return; } pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; if(l<=mid) update(now<<1,l,r,v); if(r>mid) update(now<<1|1,l,r,v); tree[now].mi=min(tree[now<<1].mi,tree[now<<1|1].mi); } int query(int now,int l,int r){ if(tree[now].l>=l&&tree[now].r<=r) return tree[now].mi; pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; int ans=0x3f3f3f3f; if(l<=mid) ans=min(ans,query(now<<1,l,r)); if(r>mid) ans=min(ans,query(now<<1|1,l,r)); return ans; } int main(){ scanf("%d%d",&n,&m); for(register int i=1;i<=n;i++) scanf("%d",&val[i]); build(1,1,n); for(register int i=1;i<=m;i++){ scanf("%d%d%d",&d,&s,&t); ask=d; re=query(1,s,t); if(ask>re){ no=i; flag=true; break; } else update(1,s,t,-d); } if(flag) printf("-1 %d",no); else printf("0 "); return 0; }