A 借教室

法一：线段树 区间修改 / 懒标记

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e6+10;

int n,m;
int w[N];
struct node{
    int l,r;
    ll lazy;
    ll minm;
}tr[N*4];

void pushdown(int u){
    auto &rt=tr[u],&le=tr[u<<1],&ri=tr[u<<1|1];
    if(rt.lazy){
        le.lazy+=rt.lazy;
        ri.lazy+=rt.lazy;
        le.minm+=rt.lazy;
        ri.minm+=rt.lazy;
        rt.lazy=0;
    }
}

void pushup(int u){
    tr[u].minm=min(tr[u<<1].minm,tr[u<<1|1].minm);
}

void build(int u,int l,int r){
    tr[u]={l,r,0,10000000000};
    
    if(l==r) {
        tr[u].minm=w[l];
        return ;
    }
    
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int v){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].lazy+=v;
        tr[u].minm+=v;
    }
    else{
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,v);
        if(r>mid)  modify(u<<1|1,l,r,v);
        pushup(u);
    }
}

ll query(int u,int l,int r){
     if(tr[u].l>=l&&tr[u].r<=r) return tr[u].minm;
    
     int mid=tr[u].l+tr[u].r>>1;
     ll minm=1e10;
     
     if(l<=mid) minm=query(u<<1,l,r);
     if(r>mid)  minm=min(minm,query(u<<1|1,l,r));
    
    return minm;
}

int main(){
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    
    build(1,1,n);
    
    int f=0;
    for(int i=1;i<=m;i++){
        int d,s,t; scanf("%d%d%d",&d,&s,&t);
        modify(1,s,t,-d);
        if(query(1,s,t)<0) {  f=i;  break; }
    }
    
    if(f) {
        puts("-1");
        printf("%d\n",f);
    } 
    else puts("0");
    
    return 0;
}

法二：二分 + 差分

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e6+10;

int n, m;
int r[N],c[N];
struct node{
    int d,s,t;
}p[N];

bool check(int x){
    memset(c,0,sizeof c);
    
    for(int i=1;i<=x;i++){
        int d=p[i].d,s=p[i].s,t=p[i].t;
        c[s]+=d,c[t+1]-=d;
    }
    
    for(int i=1;i<=n;i++) {
        c[i]+=c[i-1];
        if(c[i]>r[i]) return true;
    }
    
    return false;
}

int main(){
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++) scanf("%d",&r[i]);
    
    for(int i=1;i<=m;i++) {
        int d,s,t; scanf("%d%d%d",&d,&s,&t);
        p[i]={d,s,t};
    }
    
    int l=1,r=m,f=0;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))  f=r=mid;  // 不合法
        else l=mid+1;
    }
    
    if(f)  {
        puts("-1");
        printf("%d\n",f);
    }
    else  puts("0");
    
    return 0;
}