2014 网选 广州赛区 hdu 5023 A Corrupt Mayor's Performance Art

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 1000005
using namespace std;

int c[35];
int tree[N*4];//正值表示该节点所管理的区间的颜色是纯色，-1表示的是非纯色
int n, m; 

void buildT(int ld, int rd, int p){
    if(ld <= rd){
        tree[p] = 2;//初始每一个节点的颜色全部都是2
        if(ld == rd) return;
        int mid=(ld + rd)>>1;
        buildT(ld, mid, p<<1);
        buildT(mid+1, rd, p<<1|1);
    }
}

void updateT(int ld, int rd, int a, int b, int col, int p){

    if(ld > rd) return ;

    if(tree[p] == col) return ;

    if(ld == a && rd == b){
        tree[p] = col;
        return ;
    }
    int mid = (ld + rd)>>1;

    if(tree[p] != -1){// p所管的区间之前是纯色，现在不是纯色了，向下更新其孩子节点的颜色为它的颜色
        tree[p<<1] = tree[p<<1 | 1] = tree[p];
        tree[p] = -1;
    }

    if(a > mid)
        updateT(mid+1, rd, a, b, col, p<<1 | 1);
    else if(b <= mid)
        updateT(ld, mid, a, b, col, p<<1);
    else{
        updateT(ld, mid, a, mid, col, p<<1);
        updateT(mid+1, rd, mid+1, b, col, p<<1 | 1);
    }
}

int cnt;

void querryT(int ld, int rd, int a, int b, int p){
    if(ld>rd) return ; 

    if(tree[p] != -1){//一直找到纯色的区间！
        c[tree[p]]=1;
        return ;
    }

    int mid = (ld+rd)>>1;
    if(a > mid)
        querryT(mid+1, rd, a, b, p<<1 | 1);
    else if(b <= mid)
        querryT(ld, mid, a, b, p<<1) ;
    else{
        querryT(ld, mid, a, mid, p<<1);
        querryT(mid+1, rd, mid+1, b, p<<1 | 1);
    }
}

int main(){
    while(scanf("%d%d", &n, &m) && (n || m)){
        char ch[2];
        int a, b, k;
        buildT(1, n, 1);
        while(m--){
            scanf("%s", ch);
            if(ch[0] == 'P'){
                scanf("%d%d%d", &a, &b, &k);
                updateT(1, n, a, b, k, 1);
            }
            else{
                scanf("%d%d", &a, &b);
                memset(c, 0, sizeof(c));
                querryT(1, n, a, b, 1);
                int i;
                for(i=1; i<=30; ++i)
                    if(c[i]){
                         printf("%d", i);
                         break;
                    }
                for(++i; i<=30; ++i)
                    if(c[i]) printf(" %d", i);
                printf("\n");
            }
        }
    }
    return 0;
}