[BOJ] 백준 2820 자동차 공장

문제 링크

14268 내리갈굼 문제와 15782 Calculate! 2 문제와 같은 유형이다.

자세한 풀이는 링크를 들어가면 있다. 두개 다 보면 이해 간다.

세그먼트 트리를 이용하긴 하지만 쿼리는 구간이 아닌 한 정점에서만 물어보므로 lazy propagation을 단순히 O(lgN)의 시간복잡도로 해결하기 위해 사용한다.

따라서 세그먼트 트리에서 리프노드 이외의 노드의 값은 뭐가 들어있던 상관이 없기 때문에 코드의 29, 41번째 줄에서 v를 한 번만 더해줬다(리프노드에선 원래 한 번만 더해진다). 크게 상관있는 부분은 아니다.

정답 코드

	#include <iostream>
	#include <vector>
	using namespace std;
	const int N_MAX = 500001;
	using ll = long long;
	int n, m, l[N_MAX], r[N_MAX];
	ll tree[N_MAX * 4], lazy[N_MAX * 4], money[N_MAX], order[N_MAX];
	vector<vector<int>> p;
	void dfs(int now, int &o) {
	l[now] = ++o;
	for (int next : p[now]) dfs(next, o);
	r[now] = o;
	}
	void init(int node, int s, int e) {
	if (s == e) {
	tree[node] = order[s];
	return;
	}
	int m = (s + e) / 2;
	init(node * 2, s, m);
	init(node * 2 + 1, m + 1, e);
	}
	void update_lazy(int node, int s, int e) {
	if (lazy[node]) {
	tree[node] += 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 i, int j, ll v) {
	update_lazy(node, s, e);
	if (j < s || e < i) return;
	if (i <= s && e <= j) {
	tree[node] += v;
	if (s != e) {
	lazy[node * 2] += v;
	lazy[node * 2 + 1] += v;
	}
	return;
	}
	int m = (s + e) / 2;
	update(node * 2, s, m, i, j, v);
	update(node * 2 + 1, m + 1, e, i, j, v);
	}
	ll query(int node, int s, int e, int idx) {
	update_lazy(node, s, e);
	if (idx < s || e < idx) return 0;
	if (s == e) return tree[node];
	int m = (s + e) / 2;
	return query(node * 2, s, m, idx) + query(node * 2 + 1, m + 1, e, idx);
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	p.resize(n + 1);
	cin >> money[1];
	int x;
	for (int i = 2; i < n + 1; i++) {
	cin >> money[i] >> x;
	p[x].push_back(i);
	}
	int o = 0;
	dfs(1, o);
	for (int i = 1; i < n + 1; i++) {
	order[l[i]] = money[i];
	}
	init(1, 1, n);
	char c;
	ll y;
	for (int i = 0; i < m; i++) {
	cin >> c;
	if (c == 'p') {
	cin >> x >> y;
	update(1, 1, n, l[x] + 1, r[x], y);
	}
	else if (c == 'u') {
	cin >> x;
	cout << query(1, 1, n, l[x]) << '\n';
	}
	}
	}

view raw 2820.cpp hosted with ❤ by GitHub

질문 및 피드백 환영합니다.