「题解」Luogu 1083「借教室」

分析

抽象出模型就是一个区间减的线段树,查询可以直接查询根节点。

建树不要把建左右子树建成根,,,

代码

#include<cstdio>
#include<cctype>
const int MAXN = 10000000 + 6;
int read(){
    int op = 1,ans = 0;char s = getchar();
    while(!isdigit(s)){if(s == '-'){op = -1;}s = getchar();}
    while(isdigit(s)){ans = ans * 10 + s - '0';s = getchar();}
    return ans * op;
}
struct SegmentTree{
    int l,r,add,MIN;
};SegmentTree T[MAXN * 4];
inline int L(int x){return x << 1;}
inline int R(int x){return x << 1 | 1;}
inline int mid(int l,int r){return (l + r) >> 1;}
inline int min(int a,int b){return a < b ? a : b;}
inline void maintain(int p){T[p].MIN = min(T[L(p)].MIN,T[R(p)].MIN);}
void build(int p,int l,int r){
    T[p].l = l,T[p].r = r;
    if(l == r){
        T[p].MIN = read();
        return;
    }
    build(L(p),l,mid(l,r));
    build(R(p),mid(l,r) + 1,r);
    maintain(p);
}
void spread(int p){
    if(T[p].add){
        T[L(p)].MIN += T[p].add;
        T[R(p)].MIN += T[p].add;
        T[L(p)].add += T[p].add;
        T[R(p)].add += T[p].add;
        T[p].add = 0;
    }
}
void change(int p,int l,int r,int k){
    if(l <= T[p].l && T[p].r <= r){
        T[p].MIN += k;
        T[p].add += k;
        return;
    }
    spread(p);
    if(l <= mid(T[p].l,T[p].r)) change(L(p),l,r,k);
    if(r > mid(T[p].l,T[p].r)) change(R(p),l,r,k);
    maintain(p);
}
int main(){
    //freopen("in.txt","r",stdin);
    int n,m,d,s,t;n = read();m = read();
    register int i;
    build(1,1,n);
    for(i = 1;i <= m;i++){
        d = read();s = read();t = read();
        change(1,s,t,-d);
        if(T[1].MIN < 0){printf("-1\n%d",i);return 0;}
    }
    printf("0");

    return 0;
}