线段树（区间合并）HDU

题意：输入n,m，给定n个相互连通的村庄，有m个操作，D x,表示破坏x村庄使其与相邻的两个村庄不相通，R 表示修复上一个被破坏的村庄，与相邻的两个村庄联通。Q x表示与x相连的村庄有多少个。

思路：一开始只知道是线段树，想着肯定得用结构体记录每个点的信息，怎么记录就不知道了。然后学了线段树区间合并。

首先要知道结构体记录的信息，当前区间的左右边界、左右边最大连续区间、总的最大连续区间、长度。

那么对于初始化就知道了。

然后看pushdown函数，直到左右儿子信息要更新父节点的信息（详细看注释）

线段树的更新就是单点修改，当找到要更新的节点时，就要更新这个节点的信息了。同时利用回溯pushdown。

单点查询：如果能找到那个点，就返回最大连续区间长度，对于查询写了个式子，模模糊糊有点理解：（也就是说，如果处在左儿子的右边最大区间，该右边最大区间和右儿子最大连续左区间一定相连（这是性质），加上即可

#include<stdio.h>

#include<stack>

#include<string.h>

using namespace std;

struct node

{

    int l,r,ls,rs,sum,len;

}ans[200010];/*记录 左端最大连续区间 右端最大连续区间 最大连续区间*/

void pushdown(int o)

{

    ans[o].ls=ans[o<<1].ls;

    ans[o].rs=ans[o<<1|1].rs;

    ans[o].sum=max(ans[o<<1|1].sum,ans[o<<1].sum);

    if(ans[o<<1].ls==ans[o<<1].len)/*如果左儿子区间全都相连*/

        ans[o].ls+=ans[o<<1|1].ls;/*加上右儿子的左区间*/

    if(ans[o<<1|1].rs==ans[o<<1|1].len)/*同理*/

        ans[o].rs+=ans[o<<1].rs;

}

void build(int l,int r,int o)/*初始化*/

{

    ans[o].l=l,ans[o].r=r;

    ans[o].len=(r-l+1);

    ans[o].ls=ans[o].rs=ans[o].sum=1;/*r-l+1*/

    if(l==r)

        return;

    int mid=(l+r)>>1;

    build(l,mid,o<<1);

    build(mid+1,r,o<<1|1);

    pushdown(o);

    return ;

}

void update(int o,int x,int judge)/*单点修改*/

{

    if(ans[o].l==ans[o].r)

    {

        ans[o].sum=ans[o].ls=ans[o].rs=judge;

        return ;

    }

    int mid=(ans[o].l+ans[o].r)>>1;

    if(x<=mid) update(o<<1,x,judge);

    else update(o<<1|1,x,judge);

    pushdown(o);

}

int query(int o,int x)

{

    if(ans[o].l==ans[o].r)

    {

        return ans[o].sum;/* 0 或 1*/

    }

    int mid=(ans[o].l+ans[o].r)>>1;

   // printf("%d %d\n",x,mid);/*相邻节点之间区间是连续的*/

    if(x<=mid)

    {

        /*满足这个条件好像是相连的 l+ls = r - rs +1 ,rs与ls相连 x正好是临界点  */

        if(x>=ans[o<<1].r-ans[o<<1].rs+1)/*判断x点在左儿子的左右区间*/

            return ans[o<<1].rs+ans[o<<1|1].ls;/*为什么相加??*/

        else

            return query(o<<1,x);

    }

    else

    {

        if(ans[o<<1|1].ls+ans[o<<1|1].l-1>=x)

            return ans[o<<1|1].ls+ans[o<<1].rs;

        else

            return  query(o<<1|1,x);

    }

}

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m))

    {

        build(1,n,1);

        char a[10];

        int x;

        stack<int>s;

        for(int i=1;i<=m;i++)

        {

            scanf("%s",a);

            if(a[0]=='D')

            {

                scanf("%d",&x);

                s.push(x);

                update(1,x,0);

            }

            else if(a[0]=='Q')

            {

                scanf("%d",&x);

                printf("%d\n",query(1,x));

            }

            else if(a[0]=='R')

            {

                x=s.top();

                s.pop();

                update(1,x,1);

            }

        }

    }

    return 0;

}

）

巴特西

线段树（区间合并）HDU - 1540

最新文章

热门文章