[P3] 백준 18437번 회사 문화 5 C++ 세그먼트 트리, 오일러 경로 테크닉, 느리게 갱신되는 세그먼트 트리

리뷰

 

구간 대체 업데이트, 구간 합, 느린 갱신, 오일러 경로 테크닉을 활용해야 하는 문제

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

 

전역 변수

• n, m : 직원의 수 n, 쿼리의 수 m
• MAX_N : 주어지는 n값의 최대치를 나타낼 정수형 상수 변수, 100001로 초기화 한다.
• tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화
• lazy : 세그먼트 트리 업데이트 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화
• path : 부하 직원을 인접리스트로 저장할 정수형 벡터, MAX_N크기로 초기화
• it : 서브 트리에서 해당 노드에 진입한 시간을 기록할 정수형 배열, MAX_N크기로 초기화
• ot : 서브 트리에서 해당 노드에서 빠져나온 시간을 기록할 정수형 배열, MAX_N크기로 초기화
• timer : 시간 정보를 저장할 정수형 변수

 

함수

1. dfs

void dfs(int boss)

 

각 직원에 다다른 시간을 저장할 깊이 우선 탐색 함수

1. boss를 매개변수로 받아 it[boss]에 timer + 1값을 저장한다.
2. 자신의 인접리스트에 존재하는 자식 노드에게 dfs를 수행한다.
3. 모든 자식에게 재귀가 마친 후에 ot[boss]에 timer값을 저장한다.

 

2. build

void build(int node, int s, int e)

 

세그먼트 트리에 초깃값을 적용시킬 함수

1. 세그먼트 트리의 리프노드에 1을 저장하고 각 상위 노드에 구간합을 저장해 준다.

 

3. propagate

void propagate(int node, int s, int e)

 

갱신할 업데이트가 있는지 확인하고 있다면 구간 업데이트를 진행해 주는 함수

1. 현재 노드에 lazy값이 존재하다면 업데이트를 진행해 준다.
2. lazy값이 1이라면 현재 노드를 구간의 길이로 변경해 준다.
3. lazy값이 -1이라면 현재 노드를 0으로 변경해 준다.
4. 현재 노드가 리프노드가 아니라면 하위 노드에 lazy값을 전파해 준다.
5. 전파를 마친 후에는 현재 노드의 lazy값을 0으로 초기화 해준다.

 

4. update

void update(int node, int s, int e, int L, int R, int val)

 

구간 업데이트를 진행할 함수

1. 함수가 호출되면 현재 노드와 탐색 범위를 propagate의 매개변수로 전달하여 실행해 준다.
2. 업데이트 범위를 벗어나면 return 처리해 준다.
3. 업데이트 범위에 들어왔다면 lazy에 val을 전달해 준 후에 propagate를 실행해 준 뒤 리턴해 준다.
4. 범위가 걸칠 경우 이분 탐색을 통해 좌우로 업데이트를 재귀로 수행해 준다.
5. 재귀가 모두 완료되었을 경우 세그먼트 트리에 저장된 구간합을 업데이트 해준다.

 

5. query

int query(int node, int s, int e, int L, int R)

 

구간합을 구한 뒤 리턴해 주는 함수

1. 마찬가지로 함수가 호출되면 propagate 함수를 호출해 남아있는 업데이트를 적용시켜 준다.
2. 범위를 벗어나면 0을 리턴해 준다.
3. 유효한 범위일 경우 세그먼트 트리에 저장된 현재 노드의 값을 리턴해 준다.
4. 범위가 걸칠 경우 이분탐색을 통해 재귀적으로 왼쪽 및 오른쪽의 값을 구한 뒤 더해서 리턴해 준다.

 

문제풀이

1. n값을 입력 받아 인접리스트를 역방향으로 만들어 준다.
2. build함수를 통해 세그먼트 트리를 기본값인 1로 업데이트 해준다.
3. dfs함수를 통해 대표 번호인 1을 매개변수로 전달하여 it, ot배열을 최신화 해준다.
4. m값을 입력 받아 m개 만큼의 while문을 실행하고 order 및 idx값을 입력 받는다.
5. order가 1일 경우 it[idx] + 1, ot[idx]까지의 범위에 lazy값을 1로 전달한다.
6. order가 2일 경우 it[idx] + 1, ot[idx]까지의 범위에 lazy값을 2로 전달한다.
7. order가 3일 경우 it[idx] + 1, ot[idx]까지의 범위의 구간합을 출력해 준다.

 

참고 사항

• 가장 처음에 컴퓨터는 켜져있는 상태이다.
• 모든 쿼리는 자기 자신을 포함하지 않는다.

 

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

int n, m;
const int MAX_N = 100001;
int tree[MAX_N * 4];
int lazy[MAX_N * 4];

vector<int>path[MAX_N];
int it[MAX_N];
int ot[MAX_N];
int timer;

void dfs(int boss) {
	it[boss] = ++timer;
	for (int child : path[boss]) dfs(child);
	ot[boss] = timer;
}

void build(int node, int s, int e) {
	if (s == e) tree[node] = 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]) {
		if (lazy[node] == 1) {
			tree[node] = e - s + 1;
		}
		else if (lazy[node] == -1) {
			tree[node] = 0;
		}
		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);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int boss; cin >> boss;
		path[boss].push_back(i);
	}

	build(1, 1, n);
	dfs(1);

	cin >> m;
	while (m--) {
		int order, idx; cin >> order >> idx;
		if (order == 1) update(1, 1, n, it[idx] + 1, ot[idx], 1);
		else if (order == 2) update(1, 1, n, it[idx] + 1, ot[idx], -1);
		else cout << query(1, 1, n, it[idx] + 1, ot[idx]) << "\n";
	}
}