POJ 1823 Hotel 線段樹 + lazy標簽

題意：有一些房間，對這些房間有三種操作，一是一段連續的房間住人，二是一段連續的房間變空，三是詢問這些房間中最長的一段連續的房間是多長。
思路：明顯是線段樹的題目，中間用到了lazy思想，好題中的好題啊。挺難的一道題目，需要好好思考。這道題的關鍵之處在於，用lazy向下更新完之後，父結點的信息還需要根據子結點的信息來改變。也就是說，同時需要從下向上更新。
代碼：
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
 
const int N = 16050; 
struct tree 
{ 
    int lp,rp,llen,rlen,mlen,flag; 
    int getmid() 
    { 
        return (lp + rp) / 2; 
    } 
}tt[N * 4]; 
void built_tree(int lp,int rp,int pos) 
{ 
    tt[pos].lp = lp; 
    tt[pos].rp = rp; 
    tt[pos].flag = 0; 
    if(lp == rp) 
    { 
        tt[pos].llen = tt[pos].rlen = tt[pos].mlen = 1; 
        return; 
    } 
    int mmid = tt[pos].getmid(); 
    built_tree(lp,mmid,pos*2); 
    built_tree(mmid+1,rp,pos*2+1); 
    tt[pos].llen = tt[pos].rlen = tt[pos].mlen = tt[pos*2].mlen + tt[pos*2+1].mlen; 
} 
int max(int a,int b) 
{ 
    return a > b ? a : b; 
} 
void update(int pos) 
{ 
    if(!tt[pos*2].flag) 
        tt[pos].llen = tt[pos*2].mlen + tt[pos*2+1].llen; 
    else 
        tt[pos].llen = tt[pos*2].llen; 
    if(!tt[pos*2+1].flag) 
        tt[pos].rlen = tt[pos*2].rlen + tt[pos*2+1].mlen; 
    else 
        tt[pos].rlen = tt[pos*2+1].rlen; 
    int max1 = max(tt[pos].llen,tt[pos].rlen); 
    int max2 = tt[pos*2].rlen + tt[pos*2+1].llen; 
    int max3 = max(tt[pos*2].mlen,tt[pos*2+1].mlen); 
    tt[pos].mlen = max(max1,max(max2,max3)); 
    if(tt[pos*2].flag == tt[pos*2+1].flag) 
        tt[pos].flag = tt[pos*2].flag; 
} 
void insert(int lp,int rp,int pos) 
{ 
    if(tt[pos].lp == lp && tt[pos].rp == rp) 
    { 
        tt[pos].flag = 2; 
        tt[pos].llen = tt[pos].rlen = tt[pos].mlen = 0; 
        return; 
    } 
    if(!tt[pos].flag) 
    { 
        tt[pos].flag = 1; 
        tt[pos*2].flag = tt[pos*2+1].flag = 0; 
        tt[pos*2].llen = tt[pos*2].rlen = tt[pos*2].mlen = tt[pos*2].rp - tt[pos*2].lp + 1; 
        tt[pos*2+1].llen = tt[pos*2+1].rlen = tt[pos*2+1].mlen = tt[pos*2+1].rp - tt[pos*2+1].lp + 1; 
    } 
    int mmid = tt[pos].getmid(); 
    if(rp <= mmid) 
    { 
        insert(lp,rp,pos*2); 
    } 
    else if(lp > mmid) 
    { 
        insert(lp,rp,pos*2+1); 
    } 
    else 
    { 
       insert(lp,mmid,pos*2); 
       insert(mmid+1,rp,pos*2+1); 
    } 
    update(pos); 
} 
void rem(int lp,int rp,int pos) 
{ 
    if(tt[pos].lp == lp && tt[pos].rp == rp) 
    { 
        tt[pos].flag = 0; 
        tt[pos].llen = tt[pos].rlen = tt[pos].mlen = tt[pos].rp - tt[pos].lp + 1; 
        return; 
    } 
    if(tt[pos].flag == 2) 
    { 
        tt[pos].flag = 1; 
        tt[pos*2].flag = tt[pos*2+1].flag = 2; 
        tt[pos*2].llen = tt[pos*2].rlen = tt[pos*2].mlen = 0; 
        tt[pos*2+1].llen = tt[pos*2+1].rlen = tt[pos*2+1].mlen = 0; 
    } 
    int mmid = tt[pos].getmid(); 
    if(rp <= mmid) 
        rem(lp,rp,pos*2); 
    else if(lp > mmid) 
        rem(lp,rp,pos*2+1); 
    else 
    { 
        rem(lp,mmid,pos*2); 
        rem(mmid+1,rp,pos*2+1); 
    } 
    update(pos); 
} 
int main() 
{ 
    //freopen("1.txt","r",stdin); 
    int n,m; 
    while(scanf("%d%d",&n,&m) != EOF) 
    { 
        int id,x,y; 
        built_tree(1,n,1); 
        while(m--) 
        { 
            scanf("%d",&id); 
            if(id == 3) 
                printf("%d\n",tt[1].mlen); 
            else if(id == 1) 
            { 
                scanf("%d%d",&x,&y); 
                insert(x,x+y-1,1); 
            } 
            else 
            { 
                scanf("%d%d",&x,&y); 
                rem(x,x+y-1,1); 
            } 
        } 
    } 
    return 0; 
}