【 在线+线段树 】借教室

貌似这道题的做法很多，这里记录的是利用线段树算法解决这道题。

题意： 共有n天，每天可以用于借出的教室的数量为 a[i] ，有m个订单，每个订单每天都有相同的借教室的需求。借教室按照先来后到的原则，所以可能后续的订单无法满足，如果有就输出无法满足的那一个订单编号，反之都能满足就输出-1.

分析：

1. 由于订单对每天的教室需求都相同，所以，对于每一个订单我们可以处理一个区间，将订单开始那一天和结束那一天的同时加上/减去同一个数字就可以了。
2. 什么时候出现无法满足的情况？？？当对区间操作后只要出现了了一个 剩余教室<0 的情况
3. 怎么快速地处理 剩余教室<0 ? 如果区间最小值>0，那么这个区间的教室都是>0的，反之，只要最小值小于0，那就肯定不能满足需求

综上，用线段树维护区间最小值就可以了

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+12;
int sum[N],a[N],lazy[N],n,m;
void pushdown(int x)
{
  if( !lazy[x] ) return;
    sum[x<<1]-=lazy[x];
    sum[x<<1|1]-=lazy[x];
  lazy[x<<1]+=lazy[x];
  lazy[x<<1|1]+=lazy[x];
  lazy[x]=0;
}
int update(int x,int l,int r,int L,int R,int v)
{
  if( L<=l and r<=R ) { lazy[x]+=v;sum[x]-=v;return sum[x]; }
  int mid=l+r>>1;
  pushdown( x );
  if( L<=mid ) sum[x]=min(sum[x],update( x<<1,l,mid,L,R,v ));
  if( R>mid  ) sum[x]=min( sum[x] , update( x<<1|1,mid+1,r,L,R,v ) );
  return sum[x];
}
int build(int x,int l,int r)
{
  if(l==r) return sum[x]=a[l];
  int mid=l+r>>1;
  return sum[x]=min( build( x<<1,l,mid ) , build(x<<1|1,mid+1,r) ) ;
}
int main(){
  cin>>n>>m;
  int l,r,v;
  for(int i=1;i<=n;i++) cin>>a[i];
  build(1,1,n);
  for(int i=1;i<=m;i++)
  {
    cin>>v>>l>>r;
    int p=update(1,1,n,l,r,v);
    if( p<0 )
    {
      cout<<-1<<endl<<i;
      return 0;
    }
  }
  cout<<0;

}