[线段树区间更新]poj 1823

题意

? ? ?一个旅馆有n个房间，有m次操作，每次操作可以是 1，从第a个房间开始的连续b个房间全部住满 2：从a开始的b个房间全部清空 3：查询n个房间中最长连续空房间的长度。

?

思路

? ? ?对于每个节点，记录这个节点的sta：状态，val：最长连续空房 lmx：区间内左侧连续空房间数 rmx：区间内右侧连续空房间数。并用子节点的值来更新父节点。

? ? 更新节点时，记得用子节点的状态更新当前节点的sta值，否则父节点更新时会出错。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 1000000;
struct{
    int l,r,val,lmx,rmx,sta;   //0empty 1full -1mix
}node[3*nMax];

void gao(int u){
    if(node[u].sta == 0){
        node[u].val = node[u].lmx = node[u].rmx =  node[u].r - node[u].l + 1;
    }else{
        node[u].val = node[u].lmx = node[u].rmx =0;
    }
}
void build(int l ,int r ,int u){
    node[u].l = l;
    node[u].r = r;
    node[u].sta = 0;
    gao(u);
    if(l == r){
        return;
    }
    int m = (l+r)>>1;
    build(l ,m ,u*2);
    build(m+1 ,r ,u*2 + 1);
}
void update(int left ,int right ,int ope ,int u){
    int l = node[u].l;
    int r = node[u].r;
    if(l == left && r == right){
        node[u].sta = ope;
        gao(u);
        return;
    }
    if(node[u].sta == ope)return ;
    if(node[u].sta != -1){
        node[2*u].sta = node[2*u+1].sta = node[u].sta;
        gao(u*2),gao(u*2+1);
        node[u].sta = -1;
    }
    int m = (l + r)>>1;
    if(right <= m){
        update(left ,right ,ope ,u*2);
    }else{
        if(left >= m + 1){
            update(left ,right ,ope ,u*2+1);
        }else{
            update(left ,m ,ope ,u*2);
            update(m+1,right ,ope ,u*2+1);
        }
    }
    if(node[u*2].sta == 0){
        node[u].lmx = node[u*2].val + node[u*2+1].lmx;
    }else{
        node[u].lmx = node[u*2].lmx;
    }

    if(node[u*2+1].sta == 0){
        node[u].rmx = node[u*2+1].val + node[u*2].rmx;
    }else{
        node[u].rmx = node[u*2+1].rmx;
    }

    node[u].val = max(node[u*2].val,node[u*2+1].val);
    node[u].val = max(node[u].val,node[u*2].rmx+node[u*2+1].lmx);

    if(node[u*2].sta == node[u*2+1].sta){
        node[u].sta = node[u*2].sta;
    }
}
int main(){
    int n ,m ,ope ,a ,b ;
    while(scanf("%d%d",&n,&m)!=EOF){
        build(1 ,n ,1);
        while(m--){
            scanf("%d",&ope);
            if(ope == 1){
                scanf("%d%d",&a,&b);
                update(a ,a + b -1 ,1 ,1);
            }
            if(ope == 2){
                scanf("%d%d",&a,&b);
                update(a ,a + b -1 ,0 ,1);
            }
            if(ope == 3){
                printf("%d\n",node[1].val);
            }
        }
    }
    return 0;
}

?

[线段树区间更新]poj 1823

原文：http://bbezxcy.iteye.com/blog/2162031