【在线】【分块】 借教室

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

分析： 分块和线段树同样是相似的做法，思路几乎一样同样维护最小值，每次修改完区间后看区间最小值-lazy是不是小于零就可以了 。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+12;
int n,m;
int tot,L[N],R[N],block,a[N],lazy[N],belong[N],mi[N],l,r,x;
void build()
{
  block=sqrt(n);
  tot=n/block;
  if( n%block ) tot++;
  for(int i=1;i<=n;i++)
  {
    belong[i]=(i-1)/block+1;
    mi[ belong[i] ]=min( mi[belong[i]],a[i] );
  }
  for(int i=1;i<=tot;i++)
  {
    L[i]=(i-1)*block+1,R[i]=i*block;
  }
  R[tot]=n;
}
void add(int x,int y,int v,int now)
{
  int  ans=1;
  if( belong[x]==belong[y] )
  {
    for(int i=x;i<=y;i++)
    {
      a[i]-=v;
      ans=min(ans,a[i]-lazy[belong[i]]);
      mi[belong[i]]=min(mi[belong[i]],a[i]);
    }
  }
  else{
    for(int i=x;i<=R[belong[x]];i++)
    {
      a[i]-=v;
      ans=min(ans,a[i]-lazy[belong[i]]);
      mi[belong[i]]=min(mi[belong[i]],a[i]);
    }

    for(int i=belong[x]+1;i<belong[y];i++)
    {
      lazy[i]+=v;
      ans=min(ans, mi[i]-lazy[i] );
    }
    for(int i=L[belong[y]];i<=y;i++)
    {
      a[i]-=v;
      ans=min( ans,a[i]-lazy[belong[i]] );
      mi[ belong[i] ]=min( mi[belong[i]],a[i] );
    }
  }
  if( ans<0 ) {
    cout<<-1<<endl<<now;
    exit(0);
  }
  return;
}
int main(){

  cin>>n>>m;
  for(int i=1;i<=n;i++) mi[i]=2000000012;
  for(int i=1;i<=n;i++) cin>>a[i];
  build();
  for(int i=1;i<=m;i++)
  {
      cin>>x>>l>>r;
      add(l,r,x,i);
  }
  cout<<0;
}