LuoGu P1083 借教室

题目传送门

借教室这个题有两种做法，差分+前缀和或者是线段树

线段树维护区间最小值，因为能不能借教室使用是由这几天中可用教室最少的一天决定的

其实这题是个很裸的线段树维护区间最小值，但有一点需要注意，区间最小值在进行加减修改时不能乘以区间长度

很简单，不论区间长度怎么样，你整个区间-x，最小值也减小了x，而不会是x*length，我因为这一点WA了两次(不知为啥,最近智商捉急)

之后就A掉了

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define mid ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define min(a,b) (a<b?a:b)
#define pushup(rt) t[rt].data=min(t[ls].data,t[rs].data)

using namespace std;

const int N=1e6+5;

struct segtree{
 int left,right;
 int data,tag;
 inline int size(){return right-left+1;}
}t[(N<<2)];

int n,ans,f=true,tt;
int tot,s,cnt,v[N],m;

inline void build(int rt,int l,int r){
 t[rt].left=l;t[rt].right=r;t[rt].tag=0;
 if(l==r){
  t[rt].data=v[l];
  return ;
 }
 build(ls,l,mid);build(rs,mid+1,r);
 pushup(rt);return ;
}

inline void pushdown(int rt){
 if(t[rt].tag!=0){
  t[ls].tag+=t[rt].tag;
  t[rs].tag+=t[rt].tag;
  t[ls].data+=t[rt].tag;
  t[rs].data+=t[rt].tag;
  t[rt].tag=0;
 }
 return ;
}

inline void update(int rt,int num){
 int l=t[rt].left,r=t[rt].right;
 if(s<=l&&r<=tt){
  if(t[rt].data>=tot){
   t[rt].data-=tot;
   t[rt].tag-=tot;
  }else{
   f=false;
   ans=num;
  }
  return ;
 }
 if(!f) return ;
 pushdown(rt);
 if(s<=mid) update(ls,num);
 if(tt>mid) update(rs,num);
 pushup(rt);return ;
}

int main(){
 scanf("%d%d",&n,&m);
 for(register int i=1;i<=n;++i) scanf("%d",&v[i]);
 build(1,1,n);
 for(register int i=1;i<=m;++i){
  scanf("%d%d%d",&tot,&s,&tt);
  update(1,i);
 }
 if(f) puts("0");
 else{
  puts("-1");
  printf("%d
",ans);
 }
 return 0;
}