【 在线+线段树 】借教室

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

题意： 共有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;

}

【离线】【差分】【二分】 借教室

应该这道题的标准做法是差分+二分吧。

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

分析： 每个订单其实就是一次操作，二分操作，然后用差分快速地去更新区间内每一个元素的值就可以了，由于数据范围给的比较小，所以不会超时。

本人太懒，直接Copy一下 大佬的Code

Code

#include<iostream>
#include<cstring>
#include<cstdio> 
using namespace std;
int n,m;
int diff[1000011],need[1000011],rest[1000011],r[1000011],l[1000011],d[1000011];
bool isok(int x)
{
    memset(diff,0,sizeof(diff));
    for(int i=1;i<=x;i++)
    {
        diff[l[i]]+=d[i];
        diff[r[i]+1]-=d[i]; 
    }
    for(int i=1;i<=n;i++)
    {
        need[i]=need[i-1]+diff[i];
        if(need[i]>rest[i])return 0;
    }
    return 1;
} 
int main()
{
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&rest[i]);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&l[i],&r[i]);
    int begin=1,end=m; 
    if(isok(m)){cout<<"0";return 0;}
    while(begin<end)
    {
        int mid=(begin+end)/2;
        if(isok(mid))begin=mid+1;
        else end=mid;
    }
    cout<<"-1"<<endl<<begin;
}

【在线】【分块】 借教室

题意： 共有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;
}