借教室（线段数）

https://ac.nowcoder.com/acm/problem/16564
题意：
已知每天可以借出去的教室数量a[i],根据先到先得原则，按顺序分配教室，共有m个订单，第i个订单需要[li,ri]区间内借xi个教室，问到第几个订单开始无法满足（教室不够了）

分析：
m次区间[li,ri]进行修改xi，边修改边查询是否满足题意，这不就是练习线段树的题目吗？
首先建一颗含最小值信息的线段树，模拟题意进行区间修改，修改完后判断一下整个区间最小值是否小于0，即minx[1]是否小于0，若发现一不符合的修改，直接return 0。
暴力即优雅，记得开longlong（不建议define int long long 费时费空间）.

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long//补救措施开longlong
int n,m;
int a[1000005],lazy[4000005],minx[4000005];//懒标记数组和区间最小值数组
void build(int node,int l,int r){//建含最小值的线段树
    if(l==r){
        minx[node]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    minx[node]=min(minx[node<<1],minx[node<<1|1]);
}
void pushup(int node){//向下更新
    if(lazy[node]){
        minx[node<<1]+=lazy[node];
        minx[node<<1|1]+=lazy[node];
        lazy[node<<1]+=lazy[node];
        lazy[node<<1|1]+=lazy[node];
        lazy[node]=0;
    }
}
void update(int node,int l,int r,int start,int end,int num){//区间修改
    if(l>=start&&r<=end){
        minx[node]+=num;
        lazy[node]+=num;
        return ;
    }
    pushup(node);
    int mid=(l+r)>>1;
    if(start<=mid)update(node<<1,l,mid,start,end,num);
    if(end>mid)update(node<<1|1,mid+1,r,start,end,num);
    minx[node]=min(minx[node<<1],minx[node<<1|1]);
}
signed main()
{
    memset(minx,0x3f3f3f,sizeof(minx));//初始化最小值
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);//建树
    for(int i=1;i<=m;i++){
        int d,s,tt;
        cin>>d>>s>>tt;
        update(1,1,n,s,tt,-d);
        //for(int i=1;i<=6;i++) cout<<t[i].minn<<" ";
        if(minx[1]<0){
            cout<<-1<<endl;
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<0<<endl;
}