취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10565번 문제인 Salary Inequity이다.
문제는 아래 링크를 확인하자.

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

루트가 있는 트리에서 각 노드의 서브트리에 대한 쿼리는 Euler Tour Technique을 이용해 노드의 인덱스를 새로 부여한 다음 배열의 구간쿼리로 바꿔 처리할 수 있음을 기억하자.

문제를 해결하기 위해 구현해야 할 쿼리는 구간의 각 원소의 값을 증가시키는 쿼리와 구간의 최솟값 및 최댓값을 구하는 쿼리이다. 이는 lazy propagation을 적용한 segment tree를 이용해 해낼 수 있다.

여러 테스트케이스를 처리해야하므로 전역변수를 사용할 경우 변수의 초기화에 유의하자.

아래는 제출한 소스코드이다.

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

int T, N, Q;
int idx[1000001];
int invidx[1000001];
int ccnt[1000001];
vector<int> G[1000001];

int dfi = 1;
int dfs(int cur) {
	int childcnt = 0;
	idx[cur] = dfi;
	invidx[dfi] = cur;
	dfi++;

	for (auto& nxt : G[cur]) {
		childcnt += dfs(nxt);
	}

	ccnt[idx[cur]] = childcnt;

	return childcnt + 1;
}

int arr[1000001];
pair<int, int> seg[2097153];
int lazy[2097153];

pair<int, int> init(int L, int R, int sI) {
	if (L < R) {
		pair<int, int> pL = init(L, (L + R) / 2, sI * 2), pR = init((L + R) / 2 + 1, R, sI * 2 + 1);
		return seg[sI] = make_pair(min(pL.first, pR.first), max(pL.second, pR.second));
	}
	return seg[sI] = make_pair(arr[invidx[L]], arr[invidx[L]]);
}

void prop(int L, int R, int sI) {
	seg[sI].first += lazy[sI], seg[sI].second += lazy[sI];
	if (L < R) lazy[sI * 2] += lazy[sI], lazy[sI * 2 + 1] += lazy[sI];
	lazy[sI] = 0;
}

pair<int, int> upd(int L, int R, int qL, int qR, int qVal, int sI) {
	if (lazy[sI]) prop(L, R, sI);
	if (R < qL || qR < L) return seg[sI];
	if (qL <= L && R <= qR) {
		lazy[sI] += qVal;
		prop(L, R, sI);
		return seg[sI];
	}
	pair<int, int> pL = upd(L, (L + R) / 2, qL, qR, qVal, sI * 2), pR = upd((L + R) / 2 + 1, R, qL, qR, qVal, sI * 2 + 1);
	return seg[sI] = make_pair(min(pL.first, pR.first), max(pL.second, pR.second));
}

pair<int, int> qry(int L, int R, int qL, int qR, int sI) {
	if (lazy[sI]) prop(L, R, sI);
	if (R < qL || qR < L) return make_pair(1000000007, -1000000007);
	if (qL <= L && R <= qR) return seg[sI];
	pair<int, int> pL = qry(L, (L + R) / 2, qL, qR, sI * 2), pR = qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
	return make_pair(min(pL.first, pR.first), max(pL.second, pR.second));
}

void solve() {
	cin >> N;
	for (int i = 1; i <= N; i++) G[i].clear();
	dfi = 1;
	memset(lazy, 0, sizeof(lazy));
	for (int i = 2; i <= N; i++) {
		int x; cin >> x;
		G[x].emplace_back(i);
	}

	dfs(1);

	for (int i = 1; i <= N; i++) cin >> arr[i];

	init(1, N, 1);

	cin >> Q;
	while (Q--) {
		char q; cin >> q;
		if (q == 'R') {
			int qL, qVal; cin >> qL >> qVal;
			qL = idx[qL];
			upd(1, N, qL, qL + ccnt[qL], qVal, 1);
		}
		else {
			int qL; cin >> qL;
			qL = idx[qL];
			pair<int, int> pQ = qry(1, N, qL, qL + ccnt[qL], 1);
			cout << pQ.second - pQ.first << '\n';
		}
	}
}

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

	cin >> T;
	while (T--) solve();
}