hdu 5023 线段树+状压

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

在片段上着色，有两种操作，如下：

第一种：P a b c 把 a 片段至 b 片段的颜色都变为 c 。

第二种：Q a b 询问 a 片段至 b 片段有哪些颜色，把这些颜色按从小到大的编号输出，不要有重复

片段上默认的初始颜色为编号2的颜色。

颜色30种，状压；线段树进行更新和询问

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = 1000005;

int ans[35];

void cntbit(int x)

{

    int cnt = 0;

    for(int i = 1;i <= 30;++i){

        if(x&(1<<(i-1)))

            ans[cnt++] = i;

    }

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

        printf("%d%c",ans[i]," \n"[i == cnt-1]);

    return;

}

struct node

{

    int l,r;

    int color;//color用位1个数记录那些颜色被涂抹

    bool leaf;//当线段恰好覆盖一个节点的区间时就直接对该节操作而不再向下操作

    //对于这种线段树，要在获得整块区间时停止并把该节点的leaf改为true

}s[N*3];

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

{

    s[root].l = l;

    s[root].r = r;

    s[root].leaf = false;

    if(l == r){

        return;

    }

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

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

    build(mid+1,r,(root<<1)+1);

    return;

}

void insert(int l,int r,int root,int color)

{

    if(l == s[root].l && s[root].r == r){

        s[root].color = color;

        s[root].leaf = true;

        return;

    }

    if(s[root].leaf){

        s[root].leaf = false;

        s[root<<1].leaf = true;

        s[(root<<1)+1].leaf = true;

        s[root<<1].color = s[root].color;

        s[(root<<1)+1].color = s[root].color;

    }

    int mid = (s[root].l+s[root].r)>>1;

    if(mid >= r)

        insert(l,r,root<<1,color);

    else if(l > mid)

        insert(l,r,(root<<1)+1,color);

    else{

        insert(l,mid,root<<1,color);

        insert(mid+1,r,(root<<1)+1,color);

    }

    s[root].color = s[root<<1].color | s[(root<<1)+1].color;

}

int query(int l,int r,int root)

{

    //s[root].leaf == true的判断不能丢

    if( s[root].leaf || (s[root].l == l && s[root].r == r)){

        return s[root].color;

    }

    int mid = (s[root].l + s[root].r)>>1;

    if(r <= mid){

        return query(l,r,root<<1);

    }else if(l > mid){

        return query(l,r,(root<<1)+1);

    }else{

        return query(l,mid,root<<1) | query(mid+1,r,(root<<1)+1);

    }

}

int main()

{

    int n,q;

    while(~scanf("%d%d",&n,&q),n|q){

        build(1,n,1);

        insert(1,n,1,2);

        int l,r,col;

        char ss[5];

        while(q--){

            scanf("%s%d%d",ss,&l,&r);

            if(l > r)

                swap(l,r);

            if(ss[0] == 'P'){

                scanf("%d",&col);

                insert(l,r,1,1<<(col-1));

            }

            else{

                cntbit(query(l,r,1));

            }

        }

    }

    return 0;

}

巴特西

hdu 5023 线段树+状压

最新文章

热门文章