백준12895 화려한 마을

작성일 | In

문제 링크

  • http://icpc.me/12895

사용 알고리즘

  • 세그 레이지

시간복잡도

  • $O(Q \log N)$

풀이

$T \leq 30$입니다.

가장 간단한 풀이로는 세그먼트 트리를 T개 만들어서 레이지를 뿌리면 되지만… TLE가 납니다.

어떤 구간에 색깔이 c인 집이 있는지만 확인하면 되므로 비트로 관리해도 된다는 것을 알 수 있습니다. 또한 $T \leq 30$이기 때문에 모든 색의 정보를 int 자료형 하나에 넣어줄 수 있습니다.

구간의 or값을 관리하는 세그먼트 트리를 만들어서 레이지를 뿌려주면 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

int tree[1 << 18];
int tmp[1 << 18];

int n, t, q;

void push(int node, int s, int e){
	if(!tmp[node]) return;
	tree[node] = tmp[node];
	if(s ^ e){
		tmp[node << 1] = tmp[node];
		tmp[node << 1 | 1] = tmp[node];
	}
	tmp[node] = 0;
}

void update(int node, int s, int e, int l, int r, int v){
	push(node, s, e);
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		tmp[node] = v;
		push(node, s, e);
		return;
	}
	int m = s + e >> 1;
	update(node << 1, s, m, l, r, v);
	update(node << 1 | 1, m+1, e, l, r, v);
	tree[node] = tree[node << 1] | tree[node << 1 | 1];
}

int query(int node, int s, int e, int l, int r){
	push(node, s, e);
	if(r < s || e < l) return 0;
	if(l <= s && e <= r) return tree[node];
	int m = s + e >> 1;
	return query(node << 1, s, m, l, r) | query(node << 1 | 1, m+1, e, l, r);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> t >> q;
	update(1, 1 , n, 1, n, 1);
	while(q--){
		char op; int a, b, c; cin >> op >> a >> b;
		if(a > b) swap(a, b);
		if(op == 'C'){
			cin >> c;
			update(1, 1, n, a, b, 1 << (c-1));
		}else{
			int t = query(1, 1, n, a, b);
			int cnt = 0;
			while(t){
				cnt += (t & 1);
				t >>= 1;
			}
			cout << cnt << "\n";
		}
	}
}