HDU 5023 A Corrupt Mayor's Performance Art 線段樹 區間染色

題意：給出區間1-N。每個區間的初始顔色為2.有兩種操作：1.修改區間[a,b]内的顔色為c。2.查詢區間[a,b]内區間的顔色有哪幾個？

思路：很直接的線段樹的操作。對于每個節點，如果它管轄的區間為同一種顔色，我們就記錄其顔色。否則記錄為混合色。

注意：如果将染成的色和現在的區間的顔色相同，我們是不需要改變的。

         其實對于區間操作，都其實會有個lazy,down,up操作，需要記住。

代碼如下：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 1000100;

int N,M;
int a,b,c;
bool used[40];
char Q[2];

#define lson(o) (o<<1)
#define rson(o) ((o<<1)|1)

struct node{
    int l, r;
    int color;
} tree[MAX<<3];

void build(int L, int R, int o)
{
    tree[o].l = L;
    tree[o].r = R;
    tree[o].color = 2;
    if(L == R) return;

    int m = (L + R) >>1;
    build(L,m,lson(o));
    build(m+1,R,rson(o));
}

void down(int o)
{
    tree[lson(o)].color = tree[rson(o)].color = tree[o].color;
}

void update(int L, int R, int o, int cover)
{
    //printf("%d %d %d %d\n",o,tree[o].l,tree[o].r,cover);
    if(tree[o].color == cover)
        return;
    if(L <= tree[o].l && tree[o].r <= R){
        tree[o].color = cover;
        return;
    }
    if(tree[o].color > 0)
        down(o);

    tree[o].color = 0;
    int m = (tree[o].l + tree[o].r) >>1;
    if(L <= m)
        update(L,R,lson(o),cover);
    if(R > m)
        update(L,R,rson(o),cover);
}

void query(int L, int R, int o)
{
    if(tree[o].color > 0){
        used[tree[o].color] = true;
        return;
    }

    int m = (tree[o].l + tree[o].r) >> 1;
    if(L <= m)
        query(L,R,lson(o));
    if(R > m)
        query(L,R,rson(o));
}

int main(void)
{
    //freopen("input.txt","r",stdin);
    while(scanf("%d %d",&N,&M),N||M){
        build(1,N,1);
        for(int i = 0; i < M; ++i){
            scanf("%1s",Q);
            if(Q[0] == 'P'){
                scanf("%d %d %d",&a,&b,&c);
                update(a,b,1,c);
            }
            else{
                scanf("%d %d",&a,&b);
                memset(used,0,sizeof(used));
                query(a,b,1);

                bool sig = true;
                for(int i = 1; i <= 30; ++i){
                    if(used[i]){
                        if(sig) sig = false;
                        else putchar(' ');
                        printf("%d",i);
                    }
                }
                puts("");
            }
        }
    }
    return 0;
}