[BOJ 18437 // C++] 회사 문화 5

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 18437번 문제인 회사 문화 5이다.
문제는 아래 링크를 확인하자.

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

18437번: 회사 문화 5

주어진 회사는 트리모양의 계층구조를 가지고 있고, 한 사람을 골랐을 때 그 사람을 상사로 갖는 모든 사람들의 컴퓨터 상태를 변경해야하므로, euler tour trick을 사용하여 트리를 배열로 표현한 뒤 컴퓨터가 켜진 직원의 수를 세는 구간합 세그먼트트리를 이용해주자.

 

범위의 모든 컴퓨터를 키거나 끄는 쿼리는 lazy propagation을 이용하면 O(lgN)으로 구현할 수 있다.

 

아래는 제출한 소스코드이다.

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

int seg[262145];
int lazy[262145];

int init(int L, int R, int sI) {
	if (L == R) return seg[sI] = 1;
	return seg[sI] = init(L, (L + R) / 2, sI * 2) + init((L + R) / 2 + 1, R, sI * 2 + 1);
}

void propagate(int L, int R, int sI) {
	if (lazy[sI] == 1) seg[sI] = R - L + 1;
	else seg[sI] = 0;
	if (L < R) {
		lazy[sI * 2] = lazy[sI * 2 + 1] = lazy[sI];
	}
	lazy[sI] = 0;
}

int update1(int L, int R, int qL, int qR, int sI) { // 컴퓨터 키기
	if (lazy[sI]) propagate(L, R, sI);
	if (R < qL || qR < L) return seg[sI];
	if (qL <= L && R <= qR) {
		lazy[sI] = 1;
		propagate(L, R, sI);
		return seg[sI];
	}
	return seg[sI] = update1(L, (L + R) / 2, qL, qR, sI * 2) + update1((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int update2(int L, int R, int qL, int qR, int sI) { // 컴퓨터 끄기
	if (lazy[sI]) propagate(L, R, sI);
	if (R < qL || qR < L) return seg[sI];
	if (qL <= L && R <= qR) {
		lazy[sI] = 2;
		propagate(L, R, sI);
		return seg[sI];
	}
	return seg[sI] = update2(L, (L + R) / 2, qL, qR, sI * 2) + update2((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int rangesum(int L, int R, int qL, int qR, int sI) {
	if (lazy[sI]) propagate(L, R, sI);
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return rangesum(L, (L + R) / 2, qL, qR, sI * 2) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

vector<int> G[100001];
int id[100001];
int cnt[100001];
int idx = 1;

int dfs(int current) {
	int ret = 0;
	id[current] = idx++;
	for (auto node : G[current]) ret += dfs(node);
	cnt[current] = ret;
	return ret + 1;
}

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

	int N; cin >> N;

	int tmp; cin >> tmp;
	for (int i = 2; i <= N; i++) {
		int x; cin >> x;
		G[x].emplace_back(i);
	}

	dfs(1);

	init(1, N, 1);

	int Q; cin >> Q;
	while (Q--) {
		int q, x; cin >> q >> x;
		if (q == 1) update1(1, N, id[x] + 1, id[x] + cnt[x], 1);
		else if (q == 2) update2(1, N, id[x] + 1, id[x] + cnt[x], 1);
		else cout << rangesum(1, N, id[x] + 1, id[x] + cnt[x], 1) << '\n';
	}
}