【题目描述】

给定一排连续的房间，有两个操作：1--找到一排连续尽可能靠左的n个房间，入住房间，并输出最左的房间号，如果不存在输出0；

2--清空某个区间内房间的人 。

【分析】

非常非常经典的一道题。

ps.前两天做的这题，当时想了半天没有想好怎么去维护，后来依靠题解磕磕绊绊的过了这题。结果今天写题解的时候还是没有马上想到思路，有空重新做一次这题。

s[n][0]表示以区间左端点开始的连续空房间个数

s[n][1]表示以区间右端点结束的连续空房间个数

s[n][2]表示整个区间的连续空房间个数

s[n][3]为懒惰标记。

注意询问的时候要输出满足条件的最左的房间号，所以注意下判断的次序即可。

#include
     
      #define  N 50010#define lson l,m,n<<1#define rson m+1,r,n<<1|1using namespace std;int s[N<<2][4];int max(int a,int b,int c){    int ans=a>b?a:b;    return ans>c?ans:c;}void pushup(int n,int m){    s[n][0]=s[n<<1][0];    s[n][1]=s[n<<1|1][1];    if(s[n<<1][0]==(m-(m>>1)))    s[n][0]+=s[n<<1|1][0];    if(s[n<<1|1][1]==(m>>1))    s[n][1]+=s[n<<1][1];    s[n][2]=max(s[n<<1][2],s[n<<1|1][2],s[n<<1][1]+s[n<<1|1][0]);}void pushdown(int n,int m){    if(s[n][3]!=-1){        s[n<<1][0]=s[n<<1][1]=s[n<<1][2]=s[n][3]?0:(m-(m>>1));        s[n<<1|1][0]=s[n<<1|1][1]=s[n<<1|1][2]=s[n][3]?0:(m>>1);        s[n<<1][3]=s[n<<1|1][3]=s[n][3];        s[n][3]=-1;    }}void build(int l,int r,int n){    s[n][0]=s[n][1]=s[n][2]=r-l+1;    s[n][3]=-1;    if(l==r)return;    int m=(l+r)>>1;    build(lson);    build(rson);}void update(int ll,int rr,int f,int l,int r,int n){    if(ll==l&&rr==r){        s[n][0]=s[n][1]=s[n][2]=f?0:(r-l+1);        s[n][3]=f;        return;    }    pushdown(n,r-l+1);    int m=(l+r)>>1;    if(rr<=m)    update(ll,rr,f,lson);    else if(ll>m)    update(ll,rr,f,rson);    else    update(ll,m,f,lson),update(m+1,rr,f,rson);    pushup(n,r-l+1);}int query(int nn,int l,int r,int n){    if(l==r)return l;    pushdown(n,r-l+1);    int m=(l+r)>>1;    if(s[n<<1][2]>=nn)    return query(nn,lson);    else if(s[n<<1][1]+s[n<<1|1][0]>=nn)    return m-s[n<<1][1]+1;    return query(nn,rson);}int main(){    int n,m;    while(~scanf("%d%d",&n,&m)){        build(1,n,1);        for(int i=1;i<=m;i++){            int f,a,b;            scanf("%d",&f);            if(f==1){                scanf("%d",&a);                if(s[1][2]