hdu 5023 A Corrupt Mayor's Performance Art（线段树+位运算）

题目链接：

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

解题思路：

题目大意：

一开始所有结点的颜色均为2类，然后给你两种操作：

P a b c 

将a到b区间全部图为c类

Q a b

输出a到b区间所有点的颜色种类。

算法思想：

线段树区间更新，用位运算存储区间颜色状态。。。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0xfffffff
using namespace std;

const int N = 1000010;
struct node{
    int l,r;
    int setv;
    int color;
}tree[N<<2];

void build(int id,int l,int r){//id:index
    tree[id].l = l;
    tree[id].r = r;
    tree[id].setv = 0;
    tree[id].color = 2;
    if(l == r)
        return;
    int mid = (l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
}

void pushup(int id){
    tree[id].color = tree[id<<1].color | tree[id<<1|1].color;
}

void pushdown(int id){
    if(tree[id].setv){
        int tmp = tree[id].setv;
        tree[id<<1].color = (1<<(tmp-1));
        tree[id<<1|1].color = (1<<(tmp-1));
        tree[id<<1].setv = tree[id<<1|1].setv = tmp;
        tree[id].setv = 0;
    }
}

void update(int id,int l,int r,int val){
    if(tree[id].l >= l && tree[id].r <= r){
        tree[id].setv = val;
        tree[id].color = (1<<(val-1));
        return;
    }
    pushdown(id);
    int mid = (tree[id].l+tree[id].r)>>1;
    if(l <= mid)
        update(id<<1,l,r,val);
    if(mid < r)
        update((id<<1)|1,l,r,val);
    pushup(id);
}

int query(int id,int l,int r){
     if(tree[id].l >= l && tree[id].r <= r){
        return tree[id].color;
    }
    pushdown(id);
    int mid = (tree[id].l+tree[id].r)>>1;
    int ans = 0;
    if(l <= mid)
        ans |= query(id<<1,l,r);
    if(mid < r)
        ans |= query(id<<1|1,l,r);
    pushup(id);
    return ans;
}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m),n+m){
        build(1,1,n);
        char op[10];
        int a,b,c;
        while(m--){
            scanf("%s",op);
            if(op[0] == 'P'){
                scanf("%d%d%d",&a,&b,&c);
                update(1,a,b,c);
            }
            else{
                scanf("%d%d",&a,&b);
                int ans = query(1,a,b);
                int flag = 1;
                for(int i = 0; i < 30; i++){
                    if(ans & (1<<i)){
                        if(flag == 1)
                            printf("%d",i+1);
                        else
                            printf(" %d",i+1);
                        flag++;
                    }
                }
                printf("\n");
            }
        }
    }
    return 0;
}