[ BOJ ] 12895 : 화려한 마을 ( PLATINUM 3 ) / C

문제

민호가 관리하는 천나라에는 N개의 집이 있다. 민호는 집을 쉽게 관리하기 위해 각각의 집을 1번, 2번, … N번으로 부르기로 했다.

어느 날 미적 감각에 눈을 뜬 민호는 특정 구간의 집들의 색들을 새롭게 칠하거나, 특정 구간의 집들에 존재하는 색의 수를 알고 싶어졌다.

작업은 다음과 같은 두가지로 이루어 진다.

1. “C x y z” : x번과 y번, 그리고 그 사이에 있는 모든 집을 z번 색으로 색칠한다.
2. “Q x y” : x번과 y번, 그리고 그 사이에 있는 모든 집에 존재하는 색의 가짓수를 출력한다.

민호가 사용할 색의 종류는 (1번, 2번, … T번) 이라 하고 처음 모든 집은 1번으로 색칠되어 있다고 생각한다.

민호가 해야하는 작업을 시뮬레이션 해보는 프로그램을 작성하자.

입력

첫 번째 줄에 N, T, Q (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 30, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 개수, 사용할 색의 개수, 작업의 개수를 의미한다.

두 번째 줄부터 작업이 주어진다. 작업은 “C x y z” 또는 “Q x y” 둘 중에 하나의 형식으로 주어진다.

출력

작업이 “Q x y”일 때의 경우 x번과 y번, 그리고 그 사이에 있는 모든 집에 존재하는 색의 가짓수를 출력한다.

풀이 과정

색들의 수가 많지 않으니, 비트마스킹을 이용해서 구간 OR 세그먼트 트리를 만든다. 덮어쓰기만 하면 되는거라 Update 는 쉬웠지만, x > y 같은 경우가 들어올 수 있다는 것을 주의해야 한다.

#include <stdio.h>
#define SIZE 100001
typedef long long LL;

LL arr[SIZE] = {0,};
LL tree[SIZE*4] = {0,};
LL lazy[SIZE*4] = {0,};

void init(int start, int end, int idx) {
    lazy[idx] = -1;
    if(start == end) {
        tree[idx] = 1;
        return;
    }
    
    int mid = (start + end) / 2;
    init(start, mid, idx*2);
    init(mid +1, end, idx*2+1);
    tree[idx] = tree[idx*2] | tree[idx*2+1];
}

void update_lazy(int start, int end, int idx) {
    if (lazy[idx] != -1) {
        tree[idx] = 1 << (lazy[idx]);
        if(start != end) {
            lazy[idx*2] = lazy[idx];
            lazy[idx*2+1] = lazy[idx];
        }
        lazy[idx] = -1;
    }
}

void update_range(int start, int end, int idx, int left, int right, int color) {
    update_lazy(start, end, idx);
    if( end < left || right < start ) return;
    if( left <= start && end <= right ) {
        tree[idx] = 1 << (color);
        if(start != end) {
            lazy[idx*2] = color;
            lazy[idx*2+1] = color;
        }
        return;
    }
    
    int mid = (start + end)/2;
    update_range(start, mid, idx*2, left, right, color);
    update_range(mid + 1, end, idx*2+1, left, right, color);
    tree[idx] = tree[idx*2] | tree[idx*2+1];
}

int conv1(LL num) {
    int cnt = 0;
    while(num > 0) {
        if((num & 1) == 1) cnt++;
        num /= 2;
    }
    return cnt;
}

LL getVal(int start, int end, int idx, int left, int right) {
    update_lazy(start, end, idx);
    if(end < left || right < start) return 0;
    if(left <= start && end <= right) return tree[idx];
    
    int mid = (start+end) / 2;
    return getVal(start, mid, idx*2, left, right) | getVal(mid+1, end, idx*2+1, left, right);
}

int main(void) {
    int n, t, q;
    scanf("%d %d %d", &n, &t, &q);
    
    init(0, n-1, 1);
    
    for(int i = 0; i < q; i++) {
        getchar();
        
        char mode;
        scanf("%c", &mode);
        if(mode == 'C') {
            int x, y, z;
            scanf("%d %d %d", &x, &y, &z);
            if(x>y) {
                int tmp = x;
                x = y;
                y = tmp;
            }
            update_range(0, n-1, 1, x-1, y-1, z-1);
        }
        else {
            int x, y;
            scanf("%d %d", &x, &y);
            if(x>y) {
                int tmp = x;
                x = y;
                y = tmp;
            }
            printf("%d\n", conv1(getVal(0, n-1, 1, x-1, y-1)));
        }
    }
    return 0;
}