题目大意
给定N个连续的房间，最初的时候全部是空的，接下来m个操作，总共有一下两种操作：
1、 a:询问是不是有连续长度为a的空房间,有的话住进最左边
2 、a b:将[a,a+b-1]的房间清空
题解
基础的区间合并和覆盖问题，维护四个域:懒惰标记setv,区间最值maxv，从左端点开始的连续的最大房间数lmax,从右端点开始的连续的最大房间数rmax
主要就是要理解PushUp操作
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 50005 #define lson l,m,s<<1 #define rson m+1,r, s<<1|1 int maxv[MAXN<<2],setv[MAXN<<2],lmax[MAXN<<2],rmax[MAXN<<2]; void build(int l,int r,int s) { maxv[s]=lmax[s]=rmax[s]=r-l+1; setv[s]=-1; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); } void PushUp(int s,int m) { lmax[s]=lmax[s<<1]; rmax[s]=rmax[s<<1|1]; if(lmax[s<<1]==(m-(m>>1))) lmax[s]+=lmax[s<<1|1]; if(rmax[s<<1|1]==(m>>1)) rmax[s]+=rmax[s<<1]; maxv[s]=max(max(maxv[s<<1],maxv[s<<1|1]),rmax[s<<1]+lmax[s<<1|1]); } void PushDown(int s,int m) { if(setv[s]!=-1) { setv[s<<1]=setv[s<<1|1]=setv[s]; maxv[s<<1]=lmax[s<<1]=rmax[s<<1]=setv[s]?0:(m-(m>>1)); maxv[s<<1|1]=lmax[s<<1|1]=rmax[s<<1|1]=setv[s]?0:(m>>1); setv[s]=-1; } } void update(int ql,int qr,int d,int l,int r,int s) { if(ql<=l&&r<=qr) { maxv[s]=lmax[s]=rmax[s]=d?0:r-l+1; setv[s]=d; return; } PushDown(s,r-l+1); int m=(l+r)>>1; if(ql<=m) update(ql,qr,d,lson); if(qr>m) update(ql,qr,d,rson); PushUp(s,r-l+1); } int query(int p,int l,int r,int s) { if(l==r) return l; PushDown(s,r-l+1); int m=(l+r)>>1; if(maxv[s<<1]>=p) return query(p,lson); else if((rmax[s<<1]+lmax[s<<1|1])>=p) return m-rmax[s<<1]+1; return query(p,rson); } int main(void) { int n,m,a,b,c; scanf("%d%d",&n,&m); build(1,n,1); while(m--) { scanf("%d",&a); if(a==1) { scanf("%d",&b); if(maxv[1]<b) printf("0\n"); else { c=query(b,1,n,1); printf("%d\n",c); update(c,c+b-1,1,1,n,1); } } else { scanf("%d%d",&b,&c); update(b,b+c-1,0,1,n,1); } } return 0; }