[线段树区间合并]poj 3667

i题意

? ? ? ?和poj1823差不多，加了一个查询最左可行的位置

思路

? ? ? ?查询的时候根据不同的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 query(int val ,int u){
    if(node[u].sta == 0 && node[u].val >= val){
        return node[u].l;
    }
    if(node[u].sta == 1){
        return 0;
    }
    if(node[u].sta == -1){
        if(node[u*2].val >= val){
            return query(val ,2*u);
        }else{
            if(node[2*u].rmx + node[2*u+1].lmx >= val){
                return node[2*u].r - node[2*u].rmx + 1;
            }else{
                return query(val ,u*2 + 1);
            }
        }
    }
    return 0;
}

int main(){
    int n ,m ,a ,b ,c;
    while(scanf("%d%d",&n,&m)!=EOF){
        build(1 ,n ,1);
        while(m--){
            scanf("%d",&a);
            if(a == 1){
                scanf("%d",&b);
                c = query(b ,1);
                printf("%d\n",c);
                if(c != 0){
                    update(c ,c+b-1 ,1 ,1);
                }
            }else{
                scanf("%d%d",&b,&c);
                update(b ,b + c -1 ,0 ,1 );
            }
        }
    }
    return 0;
}

?

[线段树区间合并]poj 3667

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