[백준]화려한 마을(12895)

문제 링크 : [백준]화려한 마을(12895)

12895번: 화려한 마을

문제 설명

1번부터 N번까지의 집이 있고, 처음에는모두 1번 색으로 칠해져 있습니다.

Q개의 쿼리를 입력을 받는데 아래와 같은 처리를 합니다.

• C A B C : A번부터 B번까지의 집의 색을 C로 바꿉니다.
• Q A B : A번부터 B번까지의 집까지까지 존재하는 색의 수를 출력합니다.

입력

N(집의 갯수, 1 <= N <= 100,000)

T(색의 갯수, 1 <= M <= 30)

O A B (C)(쿼리 정보) 

2 2 4
C 1 1 2
Q 1 2
C 2 2 2
Q 1 2

 

출력

2
1

 

카테고리

#세그먼트트리 #LazyPropagation #비트마스크

 

시간 복잡도 상한

O(QlogN)

 

해결 방법

1. 구간의 값을 업데이트하고, 조회 하는 것이 세그먼트 트리를 이용하면 빠를 것 처럼 생겼습니다.
2. 특히 구간을 업데이트 해야하므로 Lazy Propagation을 사용해야 할 것 같습니다.
3. 각 집의 색깔은 30까지이므로 1을 왼쪽으로 30번 이동시켜도 int범위에서 해결이 가능합니다.
4. 즉, 색깔의 번호 만큼 1을 왼쪽으로 이동시킨 비트(1번이면 2, 2번이면 4...)를 집의 색 상태로 관리합니다.
5. 구간의 값은 세그먼트 트리 노드의 자식 노드를 or 연산한 값으로 유지시킵니다.
   1. 예를 들어, 왼쪽 자식이 1, 2번 색을 사용하였고, 오른쪽 자식이 2, 3번 색을 사용하였으면, 왼쪽 자식의 값은 6(2+4), 오른쪽 자식의 값은 12(4+8)가 되고, 부모 노드는 두 값을 or 연산한 14가 됩니다.
6. 조회를 할 때는, 세그먼트 트리 구간값을 조회한 후, 1인 비트의 갯수를 세주면 됩니다.

시간복잡도

O(QlogN)

코드

#include<iostream>
#define N 100001
using namespace std;
int n,q,t[N*4],z[N*4]={0,1},a,b,c;
char o;
void lz(int p,int l,int r){
    if(z[p]){
        t[p]=(1<<z[p]);
        if(l!=r)z[p*2]=z[p*2+1]=z[p];
        z[p]=0;
    }
}
void u(int p,int l,int r,int x,int y,int c){
    lz(p,l,r);
    if(y<l||r<x)return;
    if(x<=l&&r<=y)z[p]=c,lz(p,l,r);
    else u(p*2,l,(l+r)/2,x,y,c),u(p*2+1,(l+r)/2+1,r,x,y,c),t[p]=t[p*2]|t[p*2+1];
}
int qu(int p,int l,int r,int x,int y){
    lz(p,l,r);
    if(y<l||r<x)return 0;
    if(x<=l&&r<=y)return t[p];
    return qu(p*2,l,(l+r)/2,x,y)|qu(p*2+1,(l+r)/2+1,r,x,y);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q>>q;
    while(q--){
        cin>>o>>a>>b;
        if(a>b)swap(a,b);
        if(o=='C')cin>>c,u(1,1,n,a,b,c);
        else {
            c=qu(1,1,n,a,b);
            a=0;
            while(c)a+=c&1,c>>=1;
            cout<<a<<"\n";
        }
    }
}