HDU 1540 &&POJ 2892 Tunnel Warfare (線段樹，區間合並）.

HDU 1540 &&POJ 2892 Tunnel Warfare (線段樹，區間合並）.

~~~~

第一次遇到線段樹合並的題，又被律爺教做人。TAT.

~~~~

線段樹的題意都很好理解吧。。

題目鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=1540

http://poj.org/problem?id=2892

~~~~

我的代碼：200ms

#include
#include
#include
#include
#define N 55555
#define lson rt<<1,s,m
#define rson rt<<1|1,m+1,e
using namespace std;

int st[N];
struct node
{
    int l,r;
    int lm,rm;  //維護一個區間從左右端點開始的最長區間
}tre[N<<2];
void build(int rt,int s,int e)
{
    tre[rt].l=s;
    tre[rt].r=e;
    tre[rt].lm=tre[rt].rm=e-s+1;
    if(s==e)
        return ;
    int m=(s+e)>>1;
    build(lson);
    build(rson);
}
void update(int p,int v,int rt,int s,int e)
{
    if(s==e)
    {
        if(v) tre[rt].lm=tre[rt].rm=1; //rebuild
        else tre[rt].lm=tre[rt].rm=0;  //destroy
        return ;
    }
    int m=(s+e)>>1;
    if(p<=m) update(p,v,lson);
    else update(p,v,rson);
    tre[rt].lm=tre[rt<<1].lm;
    tre[rt].rm=tre[rt<<1|1].rm;
    
    //若lm==區間長，還要加上右孩子的lm。
    if(tre[rt<<1].lm==tre[rt<<1].r-tre[rt<<1].l+1)  
        tre[rt].lm=tre[rt<<1].lm+tre[rt<<1|1].lm;
    if(tre[rt<<1|1].rm==tre[rt<<1|1].r-tre[rt<<1|1].l+1)   //同理~
        tre[rt].rm=tre[rt<<1|1].rm+tre[rt<<1].rm;
}
int query(int q,int rt,int s,int e)
{
    //總是把查詢操作歸結到一個父親節點下的兩個孩子節點的中間區域的最長連續區間。
    if(s==e) return tre[rt].lm;
    int m=(s+e)>>1;
    int l=m-tre[rt<<1].rm;
    int r=m+1+tre[rt<<1|1].lm;
    if(q>l && q=-1)
                    update(y,1,1,1,n);
            }
            else if(str[0]=='Q')
            {
                scanf("%d",&x);
                int k=query(x,1,1,n);
                printf("%d\n",k);
            }
        }
    }
    return 0;
}

~~~~

之前參考網上代碼所寫：300ms;

#include
#include
#include
#define N 55555
#define lson rt<<1,s,m
#define rson rt<<1|1,m+1,e
using namespace std;

int st[N];
struct node
{
    int l,r;
    int lm,rm,sm; //還要維護一個區間的最長連續區間
}tre[N<<2];
void build(int rt,int s,int e)
{
    tre[rt].l=s;
    tre[rt].r=e;
    tre[rt].lm=tre[rt].rm=tre[rt].sm=e-s+1;
    if(s==e)
        return ;
    int m=(s+e)>>1;
    build(lson);
    build(rson);
}
void update(int p,int v,int rt,int s,int e)
{
    if(s==e)
    {
        if(v) tre[rt].lm=tre[rt].rm=tre[rt].sm=1;
        else tre[rt].lm=tre[rt].rm=tre[rt].sm=0;
        return ;
    }
    int m=(s+e)>>1;
    if(p<=m) update(p,v,lson);
    else update(p,v,rson);
    tre[rt].lm=tre[rt<<1].lm;
    tre[rt].rm=tre[rt<<1|1].rm;
    tre[rt].sm=max(max(tre[rt<<1].sm,tre[rt<<1|1].sm),tre[rt<<1].rm+tre[rt<<1|1].lm);
    if(tre[rt<<1].lm==tre[rt<<1].r-tre[rt<<1].l+1)
        tre[rt].lm=tre[rt<<1].lm+tre[rt<<1|1].lm;
    if(tre[rt<<1|1].rm==tre[rt<<1|1].r-tre[rt<<1|1].l+1)
        tre[rt].rm=tre[rt<<1|1].rm+tre[rt<<1].rm;
}
int query(int q,int rt,int s,int e)
{
    //到達葉子節點或是當前節點為空或為滿的情況，直接返回。
    if(s==e || tre[rt].sm==0 || tre[rt].sm==tre[rt].r-tre[rt].l+1)
        return tre[rt].sm;
    int m=(s+e)>>1;
    if(q<=m)
    {
        //若是在做孩子的右連續區間，那麼還要看右孩子的左連續區間
        if(q>=tre[rt<<1].r-tre[rt<<1].rm+1)
            return query(q,lson)+query(m+1,rson);
        else
            return query(q,lson);
    }
    else
    {
        //同理~
        if(q<=tre[rt<<1|1].lm+tre[rt<<1|1].l-1)
            return query(m,lson)+query(q,rson);
        else
            return query(q,rson);
    }
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int top=-1;
        build(1,1,n);
        for(int i=0;i=-1)
                    update(y,1,1,1,n);
            }
            else if(str[0]=='Q')
            {
                scanf("%d",&x);
                int k=query(x,1,1,n);
                printf("%d\n",k);
            }
        }
    }
    return 0;
}