hdu 5023 线段树+位运算

主要考线段树的区间修改和区间查询，这里有一个问题就是这么把一个区间的多种颜色上传给父亲甚至祖先节点，在这里题目告诉我们最多30颜色，那么我们可以把这30中颜色用二进制储存和传给祖先节点，二进制的每一位有0和1两种情况，0表示这个区间不存在这种颜色，1就表示存在，我在这里用到或运算，我们确定一个非叶子节点的值时，可以把它的两个儿子节点的值做或运算，只要某一位有1，那么这一位就是1了，这样就完成了颜色的上传。看代码吧。

建树：

struct node{

    int w,f;　　　　//w是颜色的二进制表示的值，f是懒标记

}tree[*+];

int n,m,k,t,a,b,c,ans;

void build(int l,int r,int k)

{

    tree[k].f=;

    if(l==r)

    {

        tree[k].w=(<<);　　//初始都是2，把二进制第二位变成1

        return;

    }

    int mid=(l+r)/;

    build(l,mid,k*);

    build(mid+,r,k*+);

    tree[k].w=tree[k*].w|tree[k*+].w;

}

区间修改：（区间是a到b，颜色是c）

void change_interval(int l,int r,int k)

{

    if(l>=a&&r<=b)

    {

        tree[k].f=c;　　

        tree[k].w=(<<(c-));

        return ;

    }

    if(tree[k].f)    //下传懒标记

    down(k);

    int mid=(l+r)/;

    if(mid>=a)

    change_interval(l,mid,k*);

    if(mid<b)

    change_interval(mid+,r,k*+);

    tree[k].w=tree[k*].w|tree[k*+].w;

}

区间查询：我把所有颜色都保存到了ans里

void ask_interval(int l,int r,int k)

{

    if(l>=a&&r<=b)

    {

        ans|=tree[k].w;

        return;

    }

    if(tree[k].f)

    down(k);

    int mid=(l+r)/;

    if(a<=mid)

    ask_interval(l,mid,k*);

    if(b>mid)

    ask_interval(mid+,r,k*+);

    tree[k].w=tree[k*].w|tree[k*+].w;

}

完整代码：

#include<iostream>

#include<cstring>

using namespace std;

struct node{

    int w,f;

}tree[*+];

int n,m,k,t,a,b,c,ans;

void build(int l,int r,int k)

{

    tree[k].f=;

    if(l==r)

    {

        tree[k].w=(<<);

        return;

    }

    int mid=(l+r)/;

    build(l,mid,k*);

    build(mid+,r,k*+);

    tree[k].w=tree[k*].w|tree[k*+].w;

}

void down(int k)

{

    tree[k*].f=tree[k].f;

    tree[k*+].f=tree[k].f;

    tree[k*].w=<<(tree[k].f-);

    tree[k*+].w=<<(tree[k].f-);

    tree[k].f=;

}

void change_interval(int l,int r,int k)

{

    if(l>=a&&r<=b)

    {

        tree[k].f=c;

        tree[k].w=(<<(c-));

        return ;

    }

    if(tree[k].f)

    down(k);

    int mid=(l+r)/;

    if(mid>=a)

    change_interval(l,mid,k*);

    if(mid<b)

    change_interval(mid+,r,k*+);

    tree[k].w=tree[k*].w|tree[k*+].w;

}

void ask_interval(int l,int r,int k)

{

    if(l>=a&&r<=b)

    {

        ans|=tree[k].w;

        return;

    }

    if(tree[k].f)

    down(k);

    int mid=(l+r)/;

    if(a<=mid)

    ask_interval(l,mid,k*);

    if(b>mid)

    ask_interval(mid+,r,k*+);

    tree[k].w=tree[k*].w|tree[k*+].w;

}

int main()

{

    while(cin>>n>>m)

    {

        if(!n&&!m)

        break;

        build(,n,);

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

        {

            char ch[];

            cin>>ch;

            if(ch[]=='P')

            {

                cin>>a>>b>>c;

                change_interval(,n,);

            }

            else if(ch[]=='Q')

            {

                cin>>a>>b;

                ans=;

                ask_interval(,n,);

                int ss[],cnt=; //这个ss数组是为了保存颜色，好控制格式

                memset(ss,,sizeof(ss));

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

                {

                    if(&(ans>>(i-)))

                    ss[++cnt]=i;

                }

                for(int i=;i<=cnt;i++)

                {

                    if(i!=cnt)

                    cout<<ss[i]<<' ';

                    else

                    cout<<ss[i]<<endl;

                 }

            }

        }

    }

    return ;

 }

巴特西

hdu 5023 线段树+位运算

最新文章

热门文章