백준 2820 c++ "자동차 공장" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리 자료구조를 이용해서 풀어야 되는 문제이다.

다만 이 문제만의 재미난 점은 세그먼트 index를 설정해야 되는데 그게 dfs탐색을 이용한 오일러 알고리즘을 통해

index들을 새로 정의 해야 된다.

 

또한 새로 정의된 index를 바탕으로 월급또한 같이 재정의 해야된다는 점이다.

 

DFS알고리즘을 잘 수행했따면 Propagation 으로 느린전파 알고리즘을 이용하여 Update의 범위 쿼리를 갱신해주면 문제를 풀 수 있게 된다.

여기서 필자는 1-based로 시작했기 때문에 index[a].first 가 의미하는 거는 a의 실제 index자신을 의미하므로 

a보다 부하를 원하면 index[a].first +1 을 해야된다는 점이다.

 

[코드 해설]

1. 입력 처리 (Input 함수)

• 역할:
  • 노드의 개수(N), 명령의 개수(M), 노드 값, 트리 구조를 입력받아 초기화합니다.
  • arr 벡터에는 각 노드의 값을 저장합니다.
  • list 벡터에는 트리의 계층 구조(자식 노드 정보)를 저장합니다.
• 과정:
  • 첫 번째 노드는 루트 노드로 간주합니다.
  • 각 노드의 값과 부모 노드의 정보를 입력받아 트리 구조를 설정합니다.

---

2. DFS를 이용한 트리 인덱싱 (Dfs 함수)

• 역할:
  • 트리의 각 노드를 DFS 방문 순서로 재배치하여 세그먼트 트리에 효율적으로 저장할 수 있도록 합니다.
  • index 벡터는 각 노드가 DFS 순서에서 차지하는 시작과 끝 위치를 기록합니다.
  • arr2 벡터는 DFS 순서에 따라 노드 값을 저장합니다.
• 작동 방식:
  • 루트 노드부터 DFS를 실행하며, 방문 순서를 기록하고, 자식 노드로 이동합니다.
  • 각 노드의 시작(first)과 끝(second) 인덱스를 업데이트합니다.

---

3. Lazy Propagation 처리 (Propagation 함수)

• 역할:
  • 세그먼트 트리 노드에 저장된 lazy 값을 실제 tree에 반영합니다.
  • 필요시 자식 노드에도 lazy 값을 전달합니다.
• 작동 방식:
  • 현재 노드의 lazy 값이 0이 아니면, 해당 구간의 값을 업데이트하고, 자식 노드에 lazy 값을 전달합니다.
  • 이후 현재 노드의 lazy 값을 초기화합니다.

---

4. 세그먼트 트리 초기화 (Init_Tree 함수)

• 역할:
  • DFS 순서에 따라 정렬된 arr2 값을 기반으로 세그먼트 트리를 구축합니다.
• 작동 방식:
  • 리프 노드에 각 노드의 값을 설정하고, 상위 노드는 자식 노드의 합으로 값을 설정합니다.

---

5. 구간 업데이트 (Update 함수)

• 역할:
  • 특정 구간([left, right])에 대해 값을 추가합니다.
  • lazy 값을 사용하여 업데이트 연산을 효율적으로 수행합니다.
• 작동 방식:
  • 현재 노드가 업데이트 범위에 포함되면 lazy 값을 반영하고, 구간 값을 업데이트합니다.
  • 범위가 더 좁은 경우, 자식 노드로 재귀 호출합니다.

---

6. 값 쿼리 (Query 함수)

• 역할:
  • 특정 인덱스(idx)에 해당하는 노드의 값을 출력합니다.
  • Lazy Propagation을 통해 최신 상태를 반영합니다.
• 작동 방식:
  • 구간을 탐색하며 원하는 노드에 도달하면 값을 출력합니다.

---

7. 게임 실행 (Game_Start 함수)

• 역할:
  • 트리 인덱싱(Dfs)과 세그먼트 트리 초기화(Init_Tree)를 수행합니다.
  • 이후 명령을 처리하며, 업데이트(p 명령)와 쿼리(q 명령)를 실행합니다.
• 명령 종류:
  • p a b: 노드 a의 모든 자손 노드 값에 b를 더합니다.
  • q a: 노드 a의 현재 값을 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

int N, M;
vector<pair<int, int>> index;
vector<ll> tree;
vector<ll> lazy;
vector<int> arr;
vector<ll> arr2;
vector<vector<int>> list;
int cnt = 0;

void Input() {
	cin >> N >> M;
	index.resize(N + 1);
	arr.resize(N + 1);
	arr2.resize(N + 1);
	tree.resize(N * 4);
	lazy.resize(N * 4);
	list.resize(N + 1);
		
	for (int i = 1; i <= N; i++) {
		ll num;
		cin >> num;
		arr[i] = num;
		if (i != 1) {
			int idx;
			cin >> idx;
			list[idx].push_back(i);
		}
	}
}
void Dfs(int num) {
	index[num].first = ++cnt;
	arr2[cnt] = arr[num];

	for (int next : list[num]) {
		Dfs(next);
	}

	index[num].second = cnt;
}
void Propagation(int node, int start, int end) {
	if (lazy[node] != 0) {

		tree[node] += (end - start + 1) * lazy[node];

		if (start != end) {
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
}

void Init_Tree(int node, int start, int end) {
	if (start == end) {
		tree[node] = arr2[start];
		return;
	}

	int mid = (start + end) / 2;
	Init_Tree(node * 2, start, mid);
	Init_Tree(node * 2 + 1, mid + 1, end);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void Update(int node, int start, int end, int left, int right, ll val) {
	Propagation(node, start, end);

	if (end < left || right < start)return;
	if (left <= start && end <= right) {
		lazy[node] += val;
		Propagation(node, start, end);
		return;
	}

	int mid = (start + end) / 2;
	Update(node * 2, start, mid, left, right, val);
	Update(node * 2 + 1, mid + 1, end, left, right, val);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void Query(int node, int start, int end, int idx) {
	Propagation(node, start, end);

	if (idx < start || end < idx)return;

	if (start == end) {
		cout << tree[node] << '\n';
		return;
	}

	int mid = (start + end) / 2;
	if (idx <= mid) {
		Query(node * 2, start, mid, idx);
	}
	else {
		Query(node * 2 + 1, mid + 1, end, idx);
	}
}

void Game_Start() {
	Dfs(1);
	Init_Tree(1, 1, N);

	for (int i = 0; i < M; i++) {
		char ch;
		cin >> ch;
		if (ch == 'p') {
			ll a, b;
			cin >> a >> b;
			Update(1, 1, N, index[a].first + 1, index[a].second, b);
		}
		else {
			int a;
			cin >> a;
			Query(1, 1, N, index[a].first);
		}
	}
}

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

	Input();
	Game_Start();
}