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

리뷰

 

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

더 쉬운 방법이 있는데 익숙한 방법으로 풀었다.

 

 

전역 변수

• N : 배열 크기 최대값을 저장할 상수 변수
• n : 직원의 수를 저장할 변수
• m : 칭찬의 수를 저장할 변수
• lst : 인접 리스트를 저장할 벡터 배열
• it : 오일러 경로의 진입 시간을 저장할 배열
• ot : 오일러 경로의 탈출 시간을 저장할 배열
• t : 오일러 경로의 시간을 저장할 변수
• tree : 세그먼트 트리 정보를 저장할 배열
• lazy : 업데이트 값 정보를 저장할 배열

 

함수

1. dfs

void dfs(int cur)

 

오일러 경로를 구하기 위한 함수

1. 매개 변수로 현재 직원의 번호를 전달 받는다.
2. 현재 직원의 it배열의 값에 t를 전위 증가한 값을 저장한다.
3. 현재 직원의 인접 리스트를 순회하며 dfs함수의 매개변수로 전달해 재귀를 진행한다.
4. 현재 직원의 ot배열의 값이 t값을 저장한다.

 

2. propagate

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

 

값 업데이트를 진행할 요소가 있는지 체크하기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 위치 s, e를 전달 받는다.
2. 현재 노드의 lazy배열에 값이 존재한다면, 탐색 범위 * 업데이트 값 만큼 세그먼트 트리의 현재 노드에 더해준다.
3. 리프 노드가 아니라면 좌, 우 자식 노드의 lazy값에 현재 노드의 lazy값을 더해준다.
4. 현재 노드의 lazy값을 0으로 초기화 해준다.

 

3. update

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

 

구간 업데이트를 진행하기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e, 구간 범위 L, R, 업데이트 값 V를 전달 받는다.
2. propagate에 현재 노드, 탐색 범위를 매개 변수로 전달하여 호출한다.
3. 탐색 범위가 구간 범위를 벗어난 경우 리턴 처리해 준다.
4. 탐색 범위가 구간 범위에 포함되는 경우 현재 노드의 lazy값을 V만큼 더해준다.
5. propagate에 현재 노드, 탐색 범위를 매개 변수로 전달하여 호출 후 리턴 처리해 준다.
6. 좌, 우 자식 노드로 업데이트 함수를 재귀 호출해 준다.
7. 재귀를 빠져나온 후 현재 노드의 값을 좌, 우 자식 노드의 값의 합으로 저장해 준다.

 

4. query

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

 

세그먼트 트리의 특정 인덱스 값을 구하기 위한 함수

1. 매개 변수로 현재 노드 정보 node, 탐색 범위 s, e, 인덱스 값 idx를 전달 받는다.
2. propagate에 현재 노드, 탐색 범위를 매개 변수로 전달하여 호출해 준다.
3. 리프 노드에 도달한 경우 현재 노드에 저장된 값을 출력해 준다.
4. 변수 mid에 탐색 범위의 중앙값을 구하고, idx가 mid이하라면 왼쪽, 아니면 오른쪽으로 재귀를 진행한다.
5. 재귀를 빠져나오며 받은 값을 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받아주고, 가장 첫 값은 변수 trash에 받아준다.
2. 2 ~ n번 직원을 순회하며 직속 상사 직원의 값을 입력 받아준다.
3. 직속 상사 직원의 인접 리스트에 현재 직원의 번호를 push해준다.
4. dfs함수에 사장의 번호 1을 전달하여 오일러 경로를 구해준다.
5. m개의 쿼리를 입력 받아, a직원의 it값부터 ot값까지의 범위에 b만큼의 값을 더해준다.
6. 1 ~ n번의 직원을 순회하며 query함수를 통해 i직원의 it값에 저장된 노드값을 출력해 준다.

 

트러블 슈팅

1. query함수를 호출할 때 it[i]가 아닌 i를 전달하여 Fail을 받았다. 수정 후 AC를 받았다.

 

참고 사항

• 업데이트 정보를 실시간으로 얻을 필요가 없어 세그먼트 트리가 필요한 문제는 아니다.

 

정답 코드

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

const int N = 100001;
int n, m;
vector<int> lst[N];
int it[N];
int ot[N];
int t;
int tree[N * 4];
int lazy[N * 4];

void dfs(int cur) {
	it[cur] = ++t;
	for (int next : lst[cur]) dfs(next);
	ot[cur] = t;
}

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		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 update(int node, int s, int e, int L, int R, int V) {
	propagate(node, s, e);
	if (R < s || e < L) return;
	if (L <= s && e <= R) {
		lazy[node] += V;
		propagate(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, V);
	update(node * 2 + 1, mid + 1, e, L, R, V);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

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

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

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

	dfs(1);
	while (m--) {
		int a, b; cin >> a >> b;
		update(1, 1, n, it[a], ot[a], b);
	}

	for (int i = 1; i <= n; ++i) {
		cout << query(1, 1, n, it[i]) << " ";
	}
}