这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并

题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边
2 a b:将[a,a+b-1]的房间清空
思路:记录区间中最长的空房间
线段树操作:update:区间替换 query:询问满足条件的最左断点

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define M 50005#define ls node<<1,l,m#define rs node<<1|1,m+1,rint n,m,ltree[M<<2],rtree[M<<2],mtree[M<<2],cover[M<<2];void pushdown(int node,int m){ if(cover[node]!=-1) { cover[node<<1]=cover[node<<1|1]=cover[node]; mtree[node<<1]=ltree[node<<1]=rtree[node<<1]=cover[node]?0:m-(m>>1); mtree[node<<1|1]=ltree[node<<1|1]=rtree[node<<1|1]=cover[node]?0:(m>>1); cover[node]=-1; }}void pushup(int node,int m){ ltree[node]=ltree[node<<1]; rtree[node]=rtree[node<<1|1]; if(ltree[node]==m-(m>>1)) ltree[node]+=ltree[node<<1|1]; if(rtree[node]==(m>>1)) rtree[node]+=rtree[node<<1]; mtree[node]=max(ltree[node<<1|1]+rtree[node<<1],max(mtree[node<<1],mtree[node<<1|1]));}void buildtree(int node,int l,int r){ mtree[node]=ltree[node]=rtree[node]=r-l+1; cover[node]=-1; if(l==r) return ; int m=(l+r)>>1; buildtree(ls); buildtree(rs);}void update(int L,int R,int c,int node,int l,int r){ if(L<=l&&r<=R) { mtree[node]=ltree[node]=rtree[node]=c?0:r-l+1; cover[node]=c; return ; } pushdown(node,r-l+1); int m=(l+r)>>1; if(L<=m) update(L,R,c,ls); if(m
            
             >1; if(mtree[node<<1]>=w) return query(ls,w); else if(rtree[node<<1]+ltree[node<<1|1]>=w) return (m-rtree[node<<1]+1); return query(rs,w);}int main(){ //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); buildtree(1,1,n); while(m--) { int op,a,b; scanf("%d",&op); if(op==1) { scanf("%d",&a); if(mtree[1]