[P3] 백준 12895번 화려한 마을 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리, 비트마스킹

리뷰

 

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

맞왜틀 하고 있는데 질문게시판에서 쿼리의 범위 중 L이 R보다 크게 나오는 케이스가 있다는 것을 봤다.

그걸 해결해주니 AC를 받았는데 음 문제에 기재하거나 예제에 있었으면 좋겠다는 생각이 들었다.

로직은 맞게 구현해도 이런 것 때문에 틀린다면 시간을 많이 날릴 것 같다.

 

 

전역 변수

• N : 인덱스의 최대 크기를 저장할 상수 변수
• n : 집의 개수를 저장할 변수
• t : 사용할 색의 개수를 저장할 변수
• q : 작업의 개수를 저장할 변수
• tree : 세그먼트 트리 정보를 저장할 배열
• lazy : 업데이트 정보를 저장할 배열

 

함수

1. build

void build(int node, int s, int e) {
	if (s == e) tree[node] = 1 << 1;
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = tree[node * 2] | tree[node * 2 + 1];
	}
}

 

세그먼트 트리를 초기화 하기위한 함수

 

2. propagate

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		tree[node] = lazy[node];
		if (s != e) {
			lazy[node * 2] = lazy[node];
			lazy[node * 2 + 1] = lazy[node];
		}
		lazy[node] = 0;
	}
}

 

업데이트할 값이 남아 있다면 진행하기 위한 함수

 

3. update

void update(int node, int s, int e, int L, int R, int val) {
	propagate(node, s, e);
	if (R < s || e < L) return;
	if (L <= s && e <= R) {
		lazy[node] = val;
		propagate(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, val);
	update(node * 2 + 1, mid + 1, e, L, R, val);
	tree[node] = tree[node * 2] | tree[node * 2 + 1];
}

 

세그먼트 트리의 구간 업데이트를 진행하기 위한 함수

 

4. query

int query(int node, int s, int e, int L, int R) {
	propagate(node, s, e);
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	int left = query(node * 2, s, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, e, L, R);
	return left | right;
}

 

세그먼트 트리 구간의 색깔의 개수를 구하기 위한 함수

 

문제풀이

1. n, t, q에 각각 값을 입력 받고, build함수를 통해 세그먼트 트리 초기화를 진행해 준다.
2. q개의 작업을 수행하고, 매 작업마다 변수 op, l, r에 값을 입력 받아준다.
3. l이 r보다 크게 나올 경우가 있으므로 l이 r보다 클 경우 swap을 통해 두 값을 변경해 준다.
4. op가 'C'일 경우 변수 v에 값을 추가로 입력 받고, update함수를 통해 세그먼트 트리의 l~r범위를 1 << v값으로 변경한다.
5. op가 'Q'일 경우 변수 res에 query함수를 통해 세그먼트 트리의 l~r범위를 OR 연산한 값을 저장해 준다.
6. 변수 cnt에 res의 비트가 1인 개수를 저장해 준 뒤 출력 후 줄바꿈을 수행해 준다.

 

트러블 슈팅

1. 초기에 지문의 모든 집은 1번으로 색칠되어 있다는 읽지 않아 예제가 바르게 출력되지 않았다.
2. build메서드를 추가하여 세그먼트 트리의 초기값을 1 << 1로 변경해 주니 예제가 올바르게 출력되었다.
3. 구현을 잘 했는데 계속 Fail이 출력되어 질문게시판을 보니 구간 l이 r보다 큰 경우가 있다는 것을 알게 되었다.
4. l이 r보다 클 경우 둘을 swap해주는 로직을 작성 후 제출하니 AC를 받았다.

 

참고 사항

• t가 최대 30이니 int범위 내에서 처리가 가능하다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100001;
int n, t, q;
int tree[N * 4];
int lazy[N * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = 1 << 1;
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = tree[node * 2] | tree[node * 2 + 1];
	}
}

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		tree[node] = lazy[node];
		if (s != e) {
			lazy[node * 2] = lazy[node];
			lazy[node * 2 + 1] = lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(int node, int s, int e, int L, int R, int val) {
	propagate(node, s, e);
	if (R < s || e < L) return;
	if (L <= s && e <= R) {
		lazy[node] = val;
		propagate(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, val);
	update(node * 2 + 1, mid + 1, e, L, R, val);
	tree[node] = tree[node * 2] | tree[node * 2 + 1];
}

int query(int node, int s, int e, int L, int R) {
	propagate(node, s, e);
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	int left = query(node * 2, s, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, e, L, R);
	return left | right;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> t >> q;
	build(1, 1, n);
	while (q--) {
		char op;
		int l, r;
		cin >> op >> l >> r;
		if (l > r) swap(l, r);
		if (op == 'C') {
			int v; cin >> v;
			update(1, 1, n, l, r, 1 << v);
		}
		else {
			int res = query(1, 1, n, l, r);
			int cnt = 0;
			for (int i = 0; i < 32; ++i) {
				if (res & (1 << i)) cnt++;
			}
			cout << cnt << "\n";
		}
	}
}