[P3] 백준 2820번 자동차 공장 C++ 세그먼트 트리, 오일러 경로 테크닉, 느리게 갱신되는 세그먼트 트리

리뷰

 

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

오일러 경로 테크닉을 통해 배열을 트리구조로 재정의 하고, 해당 정보를 이용해 세그먼트 트리를 만든다.

세그먼트 트리 상에서 LazyPropagation을 통해 업데이트를 진행하고 각 쿼리마다 직원의 월급을 출력하는 문제

 

 

전역 변수

• MAX_N : n이 입력될 수 있는 최대값, 500001로 초기화 한다.
• n, m : 직원의 개수 n, 쿼리의 개수 m
• nodes : 각 직원의 초기 월급을 저장할 정수형 배열
• tree : 세그먼트 트리를 저장할 정수형 배열
• lazy : 세그먼트 트리의 업데이트 정보를 저장할 정수형 배열
• it : 오일러 경로 탐색을 통해 직원의 시작 인덱스를 저장하기 위한 정수형 배열
• sal : 오일러 경로에서 구한 인덱스를 기준으로 초기 월급을 재산정 하기 위한 배열
• ot : 오일러 경로 탐색을 통해 직원의 종료 인덱스를 저장하기 위한 정수형 배열
• t : 오일러 경로 탐색 시 인덱스로 사용할 변수
• parent : 트리의 간선을 저장하기 위한 정수형 벡터

 

함수

1. dfs

void dfs(int cn)

 

오일러 경로 탐색을 통해 직원의 인덱스와 초기 월급을 초기화 하는 함수

1. 매개변수로 현재 탐색할 노드의 번호를 입력 받는다.
2. it의 cn인덱스에 t를 전위증가연산한 값을 저장해 준다.
3. sal의 t인덱스에 cn의 초기 월급인 nodes의 cn인덱스 값을 저장해 준다.
4. parent의 cn인덱스를 순회하며 자식의 노드 번호를 dfs함수의 매개변수로 전달하여 재귀를 진행한다.
5. 재귀 진행 및 for문이 종료되었다면 ot의 cn인덱스에 t값을 저장해 준다.

 

2. build

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

 

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

1. 리프 노드에 도달하면 트리의 노드값을 sal의 s인덱스로 저장해 준다.
2. 리프 노드에 도달하지 못했다면 좌 우 자식 노드로 재귀탐색을 진행해 준다.
3. 사실상 구간합은 필요가 없으나 그냥 넣어주었다.

 

3. propagate

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

 

세그먼트 트리에 느린 업데이트를 진행하는 함수

1. lazy의 노드에 값이 존재한다면 세그먼트 트리의 e - s + 1구간에 값을 더해준다.
2. 만약 리프노드가 아니라면 하위 lazy의 하위 노드에 lazy값을 전파해준다.
3. 업데이트 적용이 완료되었다면 lazy값을 0으로 초기화 해준다.

 

4. update

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

 

세그먼트 트리의 구간 업데이트를 진행할 함수

1. 함수 실행 시 현재 노드, 탐색범위를 매개변수로 전달하여 propagate함수를 실행해 준다.
2. 만약 범위를 벗어난 탐색 범위라면 리턴 처리해 준다.
3. 업데이트를 적용할 구간과 탐색 구간이 겹친다면 lazy의 노드에 val을 더해준 뒤 propagate함수를 실행하고 리턴한다.
4. 구간이 겹치지 않는다면 마찬가지로 mid로 잘라 좌, 우 자식노드로 재귀 탐색을 진행한다.

 

5. query

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

 

특정 직원의 월급을 리턴하는 함수

1. 함수 실행 시 update와 마찬가지로 propagate함수를 실행해 준다.
2. 만약 리프노드에 도달했다면 세그먼트 트리 상의 해당 노드의 값을 리턴해 준다.
3. 리프 노드가 아니라면 탐색 구간을 반으로 갈라 idx가 위치한 방향쪽으로 재귀 탐색을 진행해 준다.

 

문제풀이

1. n, m값을 입력 받고, 가장 상사인 1번 노드의 초기 월급을 nodes[1]에 입력 받는다.
2. 2 ~ n번 직원까지 반복하여 초기 월급을 nodes배열에, 상사 정보를 parent벡터에 초기화 해준다.
3. dfs함수를 가장 상사인 1번 직원부터 실행하여 it, ot, sal배열을 초기화 해준다.
4. build함수를 통해 sal배열을 기준으로 세그먼트 트리를 초기화 해준다.
5. m개의 쿼리를 수행하며 order에 p, u를 입력 받아준다.
6. order가 p일 경우 idx, val을 추가로 입력 받아 세그먼트 트리 업데이트를 진행해 준다.
7. order가 u일 경우 idx를 추가로 입력 받아 idx번째 직원의 월급을 출력해 준다.

 

참고 사항

p a x가 주어진 경우 a의 모든 부하의 월급을 x만큼 증가시킨다. (-10,000 ≤ x ≤ 10,000)

업데이트 쿼리 시 자기 자신은 포함하지 않는다, it가 자기의 뒤인 경우부터 증가시켜야 한다.

 

모든 직원의 월급은 항상 양의 정수이고 2^31-1 이하이다.

int범위 내에 문제 해결이 가능하다.

 

nodes배열에 받은 초기 월급 정보로 세그먼트 트리를 초기화 하면 안된다.

오일러 경로를 탐색하면서 직원의 인덱스가 변경되므로 sal과 같이 별도의 배열을 초기화 해주어야 한다.

 

정답 코드

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

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

int it[MAX_N];
int sal[MAX_N];
int ot[MAX_N];
int t;
vector<int> parent[MAX_N];

void dfs(int cn) {
	it[cn] = ++t;
	sal[t] = nodes[cn];
	for (int nn : parent[cn]) dfs(nn);
	ot[cn] = t;
}

void build(int node, int s, int e) {
	if (s == e) tree[node] = sal[s];
	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] += (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 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 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 >> nodes[1];
	for (int i = 2; i <= n; i++) {
		int par; cin >> nodes[i] >> par;
		parent[par].push_back(i);
	}

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

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