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

리뷰

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

오일러 경로 테크닉을 구한 인덱스를 기준으로 세그먼트 트리를 양 방향으로 업데이트를 진행하며 구간합을 구하는 문제

 

전역 변수

• MAX_N : 직원의 최대 수를 저장할 정수형 상수 변수
• n, m : 직원의 수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 m
• up_tree : 상사 방향으로 칭찬값을 저장할 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4
• down_tree : 부하직원 방향으로 칭찬값을 저장할 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4
• lazy : 세그먼트 트리에 갱신될 업데이트 값을 저장할 배열, 크기는 MAX_N * 4
• lst : 각 직원간의 상하 관계를 인접리스트 형태로 저장할 정수형 벡터 배열, 크기는 MAX_N
• it : 각 직원의 오일러 경로 탐색 시작 시간을 저장할 배열, 크기는 MAX_N
• ot : 각 직원의 오일러 경로 탐색 종료 시간을 저장할 배열, 크기는 MAX_N
• timer : 탐색 시간을 저장할 변수

 

함수

1. dfs

void dfs(int boss)

 

깊이 우선 탐색으로 오일러 경로를 탐색하며 it, ot배열을 초기화를 진행할 함수

1. 매개변수로 받은 it의 boss인덱스에 timer + 1값을 저장한다.
2. boss의 인접리스트를 탐색하며 각 부하 직원을 dfs에 매개변수로 전달하여 재귀를 진행한다.
3. 인접리스트의 재귀가 완료되면 ot의 boss인덱스에 timer값을 저장한다.

 

2. propagate

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

 

down_tree에 누적된 업데이트를 진행할 함수

1. 현재 노드에 갱신할 업데이트가 있다면 down_tree의 노드에 업데이트를 적용시켜 준다.
2. 현재 노드가 리프노드가 아니라면 하위 노드에 업데이트 값을 전파해 준다.
3. 현재 노드에 더 이상 갱신할 업데이트가 없음을 명시해 준다.

 

3. up_update

void up_update(int node, int s, int e, int idx, int val)

 

up_tree에 부하로 부터 도착한 칭찬을 적용해 주기 위한 함수

1. idx에 도달했을 경우 up_tree의 현재 노드에 val값을 더해준다.
2. idx에 도달하지 못했을 경우 이분탐색을 통한 재귀로 업데이트를 진행해 준다.
3. 재귀를 빠져나오며 up_tree의 값을 최신화 해준다.

 

4. down_update

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

 

down_tree에 상사로 부터 도착한 칭찬을 적용해 주기 위한 함수

1. 함수가 호출되었을때 propagate함수를 통해 갱신할 업데이트가 존재하다면 업데이트를 진행해 준다.
2. L, R범위와 현재 탐색 중인 범위가 겹친다면 lazy의 현재 노드에 val값을 더해준다.
3. propagate함수를 적용시켜 업데이트를 진행해 준다.
4. 탐색할 범위가 더 남았을 경우 이분 탐색을 통한 재귀로 추가 업데이트를 진행해 준다.
5. 재귀를 빠져나오며 down_tree의 값을 최신화 해준다.

 

5. up_query

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

 

부하로 부터 받은 칭찬 값의 누적합을 리턴해 주는 함수

1. L은 오일러 경로 상 자신의 탐색 시간, R은 오일러 경로 상 자신의 탐색 종료시간이다.
2. 즉 자신으로 부터 연결된 모든 부하 직원들을 탐색해 준다.

 

6. down_query

int down_query(int node, int s, int e, int idx)

 

상사로 부터 받은 칭찬 값의 누적합을 리턴해 주는 함수

1. 함수가 호출 될때마다 propagate함수를 통해 누적된 업데이트가 존재한다면 진행해 준다.
2. idx에 도달했다면 해당 노드에 저장된 값을 리턴해 준다.
3. idx에 도달하지 못했다면 이분 탐색을 통한 재귀를 진행하여 idx노드까지 이동해 준다.

 

문제풀이

1. 대표의 번호는 늘 1번이며 상사는 -1로 주어지므로 필요 없다. 해당 값을 받을 trash 변수를 초기화 한다.
2. n, m, trash값을 입력 받아주고, i = 2 ~ n의 반복문을 수행해 준다.
3. 각 반복문 마다 boss변수에 상사의 번호를 받아 lst의 boss인덱스에 i를 추가해 준다.
4. dfs함수에 매개변수로 대표번호인 1을 전달하여 it, ot배열을 초기화 해준다.
5. 칭찬을 상사로 할지 부하직원으로 할지 여부를 결정할 flag변수를 초기값 1로 초기화 한다.
6. m번의 반복문을 실행하고 order변수에 첫 값을 받아준다.
7. order가 1일 경우 idx, val을 추가로 입력 받아주고 flag가 1이라면 down_update를, 아니라면 up_update를 수행한다.
8. order가 2일 경우 idx를 입력 받아주고, down_query를 노드가 it[idx]인 상태로 수행해 준다.
9. up_query도 it[idx] ~ ot[idx] 범위로 수행해 주고 두 값을 합친 뒤 출력해 준다.
10. order가 3일 경우 flag 값을 반전시켜 준다.

 

참고 사항

• 가장 처음에는 부하 직원 방향이다.
• 직원은 1번부터 n번까지 번호가 매겨져 있다.
• 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

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

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

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

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

void up_update(int node, int s, int e, int idx, int val) {
	if (s == e) up_tree[node] += val;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) up_update(node * 2, s, mid, idx, val);
		else up_update(node * 2 + 1, mid + 1, e, idx, val);
		up_tree[node] = up_tree[node * 2] + up_tree[node * 2 + 1];
	}
}

void down_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;
	down_update(node * 2, s, mid, L, R, val);
	down_update(node * 2 + 1, mid + 1, e, L, R, val);
	down_tree[node] = down_tree[node * 2] + down_tree[node * 2 + 1];
}

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

int down_query(int node, int s, int e, int idx) {
	propagate(node, s, e);
	if (s == e) return down_tree[node];
	int mid = (s + e) / 2;
	if (idx <= mid) return down_query(node * 2, s, mid, idx);
	return down_query(node * 2 + 1, mid + 1, e, idx);
}

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

	int trash;
	cin >> n >> m >> trash;
	for (int i = 2; i <= n; i++) {
		int boss; cin >> boss;
		lst[boss].push_back(i);
	}

	dfs(1);

	int flag = 1;
	while (m--) {
		int order; cin >> order;
		if (order == 1) {
			int idx, val; cin >> idx >> val;
			if (flag) down_update(1, 1, n, it[idx], ot[idx], val);
			else up_update(1, 1, n, it[idx], val);
		}
		else if (order == 2) {
			int idx; cin >> idx;
			cout << down_query(1, 1, n, it[idx]) + up_query(1, 1, n, it[idx], ot[idx]) << "\n";
		}
		else flag ^= 1;
	}
}