P1083 借教室

题面:https://www.luogu.org/problem/P1083

一题简单的线段树(但在这题看来似乎是一种玄学算法)
开一个线段树维护区间最小值和支持区间修改即可
只要整个区间中有<0的就不行,即教室不够了.输出当前的订单号就行.

Code:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include <iostream>
#define MAXN 10000010  
#define inf 0x3f3f3f3f  
using namespace std;  
struct node{  
    int l,r;
    int add;
    int mn;  
}tree[MAXN<<2]; 
void pushup(int index){    
    tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);  
}  
void pushdown(int index){  
    if(tree[index].add){   
        tree[index<<1].mn += tree[index].add;  
        tree[index<<1|1].mn += tree[index].add;  
        tree[index<<1].add += tree[index].add;  
        tree[index<<1|1].add += tree[index].add;  
        tree[index].add = 0;  

    }  
}  
void build(int l,int r,int index){  
    tree[index].l = l;  
    tree[index].r = r;  
    tree[index].add = 0;
    if(l == r){  
        scanf("%d",&tree[index].mn);
        return ;  
    }  
    int mid = (l+r)>>1;  
    build(l,mid,index<<1);  
    build(mid+1,r,index<<1|1);  
    pushup(index);  
}  
void updata(int l,int r,int index,int val){  
    if(l <= tree[index].l && r >= tree[index].r){  
        tree[index].mn += val;   
        tree[index].add += val;

        return ;  
    }  
    pushdown(index);  
    int mid = (tree[index].l+tree[index].r)>>1;  
    if(l <= mid){  
        updata(l,r,index<<1,val);  
    }  
    if(r > mid){  
        updata(l,r,index<<1|1,val);  
    }  
    pushup(index);  
}  
int main()  
{  
    int n,m,x,y,z; 
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&z,&x,&y);
        updata(x,y,1,-z);
        if(tree[1].mn<0){
            cout<<"-1"<<endl<<i<<endl;
            return 0;

        }
    }
    cout<<"0"<<endl;
    return 0;  
}