poj 1823 Hotel 线段树，注意懒散标记，不标记就会超时滴

poj 1823 Hotel 线段树，注意懒惰标记，不标记就会超时滴

这题就491个accepted，还挺吓人的，别被吓住哈，其实我被吓住了，嘻嘻，这泥玛做也是悲剧，但看分类上说属于中等题，我就猛憋一股气，三A ，呵呵

这个题我们这需要在线段上用ml，mr，len表示左面有几个连续空位，右面有几个连续空位，中间有几个连续空位

在和并的时候注意更新规则

a[i].len=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].len,a[i*2+1].len));//这个好想 更新中间len的值
    if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1))//如果右面孩子的ml=线段长度，也就是说右面孩子是全空的，那a[i].ml就是a[i*2].mr+右边整个长度
        a[i].mr=a[i*2].mr+a[i*2+1].ml;
    else
        a[i].mr=a[i*2+1].mr;//如果说右面孩子是不是全空的，那a[i].mr久等于a[i*2+1].mr
    if(a[i*2].mr==(a[i*2].r-a[i*2].l+1))//同上
        a[i].ml=a[i*2+1].ml+a[i*2].mr;
    else
        a[i].ml=a[i*2].ml;//

还有就是懒惰标记啦，不标记就超时啦

#include<iostream>
#include<cstdio>
using namespace std;
#define N 16005
struct node{
    int l,r,ml,mr,mm,len,sign;
}a[N*4];
void build(int i,int left,int right){
    a[i].l=left;
    a[i].r=right;
    a[i].len=a[i].ml=a[i].mr=right-left+1;
    a[i].mm=0;
    a[i].sign=0;//表示这条边是否被用过
    if(left==right) return ;
    int mid=(a[i].l+a[i].r)>>1;
    build(i*2,left,mid);
    build(i*2+1,mid+1,right);
}
void insert(int i,int left,int right,int sign){
//    cout<<a[i].l<<" "<<a[i].r<<"****"<<left<<" "<<right<<endl;
    if(a[i].l>=left&&a[i].r<=right){
        a[i].sign=1;
        if(sign==1){
            a[i].len=a[i].ml=a[i].mr=0;
        }else{
            a[i].len=a[i].ml=a[i].mr=(a[i].r-a[i].l+1);
        }
        return ;
    }
    if(a[i].sign==1&&a[i].ml==0&&a[i].mr==0&&a[i].len==0){//懒惰标记
        a[i*2+1].ml=a[i*2+1].mr=a[i*2+1].len=0;
        a[i*2].ml=a[i*2].mr=a[i*2].len=0;
        a[i*2+1].sign=a[i*2].sign=1;
        a[i].sign=0;
    }
    if(a[i].sign==1&&a[i].ml==(a[i].r-a[i].l+1)&&a[i].mr==(a[i].r-a[i].l+1)&&a[i].len==(a[i].r-a[i].l+1)){//懒惰标记
        a[i*2+1].ml=a[i*2+1].mr=a[i*2+1].len=(a[i*2+1].r-a[i*2+1].l+1);
        a[i*2].ml=a[i*2].mr=a[i*2].len=(a[i*2].r-a[i*2].l+1);
        a[i*2+1].sign=a[i*2].sign=1;
        a[i].sign=0;
    }
    int mid=(a[i].l+a[i].r)>>1;
    if(right<=mid) insert(i*2,left,right,sign);
    else if(left>mid) insert(i*2+1,left,right,sign);
    else{
        insert(i*2,left,mid,sign);
        insert(i*2+1,mid+1,right,sign);
    }
    a[i].len=max(a[i*2].mr+a[i*2+1].ml,max(a[i*2].len,a[i*2+1].len));
    if(a[i*2+1].ml==(a[i*2+1].r-a[i*2+1].l+1))
        a[i].mr=a[i*2].mr+a[i*2+1].ml;
    else
        a[i].mr=a[i*2+1].mr;
    if(a[i*2].mr==(a[i*2].r-a[i*2].l+1))
        a[i].ml=a[i*2+1].ml+a[i*2].mr;
    else
        a[i].ml=a[i*2].ml;
 //   cout<<"l="<<a[i].l<<" r="<<a[i].r<<" "<<a[i].ml<<" "<<a[i].len<<" "<<a[i].mr<<endl;
}

int main(){
    int n,p,m,x,y;
    while(~scanf("%d%d",&n,&p)){
        build(1,1,n);
        while(p--){
            scanf("%d",&m);
            if(m==1){
                scanf("%d%d",&x,&y);
//                cout<<"x+y-1="<<x+y-1<<endl;
                insert(1,x,x+y-1,1);
            }else if(m==2){
                scanf("%d%d",&x,&y);
                insert(1,x,x+y-1,0);
            }
            else
            printf("%d\n",max(a[1].ml,max(a[1].len,a[1].mr)));
        }

    }
}