c언어 12895번 화려한 마을 (백준)

#include <stdio.h>
#define swap(x,y) {int t=x;x=y;y=t;} //치환

int tree[262150]={}; //10만인 경우 2.6215 을 곱해도 ㄱㅊ은 것 같습니다. 400000으로 잡아도 됩니다.
int lazy[262150]={};

int init(int s, int e, int node) { //트리를 1번째 색깔로 칠해져 있도록 초기화
	if(s==e) return tree[node] = 1;
	int m=(s+e)/2;
	return tree[node] = init(s,m,node*2) | init(m+1,e,node*2+1);
}

void lazyU(int s, int e, int node) { //미룬거 업데이트
	if(lazy[node]) {
		tree[node] = lazy[node];
		if(s!=e) {
			lazy[node*2] = lazy[node];
			lazy[node*2+1] = lazy[node];
		} lazy[node] = 0;
	} return;
}

void update(int s, int e, int node, int l, int r, int color) { //수정
	lazyU(s,e,node); //미룬게 있었다면 이것 먼저 처리
	if(s>r || e<l) return; //범위 벗어남
	if(l<=s && e<=r) { //범위에 속함
		tree[node] = color; //칠하기
		if(s!=e) { //말단노드가 아니라면 
			lazy[node*2] = color;
			lazy[node*2+1] = color;
		} return; //종료
	}
	int m=(s+e)/2; //자식노드로
	update(s,m,node*2,l,r,color); //왼쪽
	update(m+1,e,node*2+1,l,r,color); //오른쪽
	tree[node] = tree[node*2] | tree[node*2+1]; //or!!!!!!
	return;
}

int find(int s, int e, int node, int l, int r) { //찾기
	lazyU(s,e,node); //미룬거 처리
	if(s>r || e<l) return 0; //범위 벗어남
	if(l<=s && e<=r) return tree[node]; //범위에 속함
	int m=(s+e)/2; //자식노드로
	return find(s,m,node*2,l,r) | find(m+1,e,node*2+1,l,r); //or!!!!!
}

int main(void) {
	int n,m,q;
	scanf("%d %d %d",&n,&m,&q);
	init(1,n,1);
	while(q--) {
		char c;
		int x,y,z=0;
		
		scanf(" %c %d %d", &c,&x,&y);
		if(x>y) swap(x,y);
		
		if(c == 'C') {
			scanf("%d",&z);
			z = (1<<(z-1));
			update(1,n,1,x,y,z);
		}
		else if(c == 'Q') {
			x=find(1,n,1,x,y);
			while(x>0) { //비트 단위로 1인 개수 구하기 (이것이 칠해진 색깔의 개수)
				if(x&1) ++z;
				x>>=1;
			}
			printf("%d\n",z);
		}
	}
}

 

풀이 : 느리게 갱신되는 세그먼트 트리, 비트마스킹

 

칠할 수 있는 색깔의 최대치는 30개입니다. 즉 이것은 int형 으로 처리할 수 있습니다 (signed int는 32비트, 여기서 1비트를 빼면 31 비트)

 

즉 첫번 째 색깔을 나타낼 때는 1번째 비트를 1로 , 열 번 째 색깔을 나타낼 때는 10번째 비트를 1로 처리해주면 됩니다.

 

특정 구역에 여러 색깔이 칠해져 있는지를 확인하려면, 구간합을 구하는 세그먼트트리처럼 + 를 하는 것이 아니라 

| (or) 연산을 해줘 비트가 1인 것들이 몇 개 인지를 하나로 모아 둔 뒤, 1개씩 세면 답을 구할 수 있게 됩니다.

 

고로 이 문제에서 주의 할점은, 세그먼트 트리를 갱신하거나, 탐색할 때, 자식노드끼리의 값들을 더하는 것이 아니라, or 비트 연산을 해주어야 합니다.

 

또한 'C' 쿼리, 즉 갱신 쿼리를 (update) 처리 할 때 색깔을 의미하는 값을 고대로 사용하기보다, 비트마스킹에 유리한 형태인, ...1....   int형 자료에서 1개만 1인 수로 변환해 주는 것이 좋습니다.

 

예로써 첫번째 색깔이라면 1번째 비트 (최하위비트부터 본다면)만 1인 수를 ,    세 번째 색깔이라면 3번째 비트만 1인수로 준비해 줍니다. 이는 shift 연산을 통해 간단히 얻어낼 수 있습니다. (빠르기도 합니다)

 

https://www.acmicpc.net/problem/12895