※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 10565번 문제인 Salary Inequity이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/10565
10565번: Salary Inequity
There is a large company of N employees. With the exception of one employee, everyone has a direct supervisor. The employee with no direct supervisor is indirectly a supervisor of all other employees in the company. We say that employee X is a subordinate
www.acmicpc.net
루트가 있는 트리에서 각 노드의 서브트리에 대한 쿼리는 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();
}728x90
'BOJ' 카테고리의 다른 글
| [BOJ 21318 // C++] 피아노 체조 (0) | 2024.02.03 |
|---|---|
| [BOJ 16401 // C++] 과자 나눠주기 (0) | 2024.02.02 |
| [BOJ 1888 // C++] 곰팡이 (0) | 2024.01.31 |
| [BOJ 1388 // C++] 바닥 장식 (1) | 2024.01.30 |
| [BOJ 11123 // C++] 양 한마리... 양 두마리... (1) | 2024.01.29 |