문제
승범이는 평소 래퍼 도끼를 흠모해왔지만, 도끼만큼 랩을 잘할 수 없다는 것을 깨닫고 도끼만큼 돈이라도 벌자는 결심을 한다. 그래서 휴학 후 ㈜승범이네를 창업했다.
㈜승범이네는 판매원들로만 이루어진 다단계 회사이다.
승범이를 제외한 모든 판매원은 사수가 배정되는데, 사수는 한 회원당 단 한 명씩만 배정된다. 만약 판매원 A가 B의 사수라면, B를 A의 부사수라고 부른다.
㈜승범이네의 수익구조는 기형적이다.
판매원들은 제품을 자비로 사서 판매한다. 이때 제품을 구매가격보다 저렴하게 판매하게 되면 손해를 보게 되는데, 어떤 회원 A가 손해를 보면 그 회원의 모든 부사수도 같은 만큼의 손해를 보게 된다. 그러면 부사수들의 부사수들도 손해를 보게 되고, 그들의 부사수들도 손해를 보게 되고, … ,결국 A와 A 밑의 모든 판매원이 A가 잃은 만큼의 손해를 보게 된다.
반대로 판매원 A가 제품을 비싸게 팔아 이익이 생길 경우, A와 A밑의 모든 판매원이 같은 이익을 얻을 수 있다.
승범이는 직원들이 현재 얼마만큼 돈을 벌었는지 감시하기 위해 다음 두 종류의 명령을 처리하려고 한다.
- 1 i w : 직원 i가 w만큼 이익/손해를 본다. (이익은 양수로, 손해는 음수로 주어진다)
- 2 i : 직원 i의 현재 통장 잔액을 출력한다.
직원들은 빈 통장을 갖고 일을 시작하며, 이익과 손해가 실시간으로 통장에 기록된다. 물론 통장 잔액은 음수일 수도 있다.
일을 시작하기 직전에 플래티넘 승급전을 남겨두고 온 것을 떠올린 승범이는 우리에게 일을 맡기고 집으로 달려가버렸다.
만년 골드 승범이를 위해 문제를 대신 해결해주자.
입력
첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다.
두 번째 줄에 판매원 1번부터 N번까지의 사수가 순서대로 공백으로 구분되어 주어진다. 승범이는 사수가 없으므로 -1이 주어진다.
세 번째 줄부터 M개의 줄에 걸쳐 위에서 설명한 명령(i, w는 정수, 1 ≤ i ≤ N, -10,000 ≤ w ≤ 10,000) 이 주어진다.
출력
2번 명령이 주어질 때마다 한 줄에 하나씩 해당하는 직원 i의 잔고 상황을 출력한다.
트리로 구성된 승범이네 주식회사는 사수가 이익이나 손해를 보면 부사수가 똑같이 그 이익과 손해를 보는 구조입니다.
매번 1번쿼리, 즉 업데이트를 수행할때 모든 부사수에대해 업데이트를 진행하면 너무 오래걸립니다.
따라서 lazy배열을 두고 느리게 갱신되는 방식으로 세그먼트트리에서 쿼리를 수행하면 됩니다.
가장 중요한 아이디어는 1번부터N명까지 사수/부사수 관계가 주어질 때,
1번 사람에게 업데이트를 진행하면 1번의 모든 부사수를 포함하는 인덱스를 반환하는 인덱싱작업이 필요하다는것입니다.
예를들어 5명의 사람 인덱스가 존재하고
1번 사수의 부사수가 2,3,4,5
2번 사수의 부사수가 4라고 하면
1번사수를 업데이트할때는 1번부터5번까지 업데이트해야하고,
2번사수를 업데이트할땐 2번부터 4번까지 업데이트 해야합니다.
세그먼트 트리에서 적용해야하므로,
dfs를 사용해서 dfs(1)=5 를 출력하고, dfs(2)=4를 출력하게 업데이트하면 됩니다.
그렇게만들면 1번사람을 업데이트하면 1~5까지 모두 업데이트가 가능하고 ,2번사람을 업데이트하면 2,4만 업데이트가 가능한 세그먼트트리를 만들 수 있습니다.
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int N, M, lazy[400004], seg[400004], idx = 1, from[100001], to[100001];
vi adj[100001];
void index(int k) {
from[k] = idx++;
for (int r : adj[k]) {
index(r);
}
to[k] = idx - 1;
}
void propagate(int n,int f,int t) {
if (lazy[n]) {
if (f != t) {
lazy[n * 2] += lazy[n];
lazy[n * 2 + 1] += lazy[n];
}
seg[n] += lazy[n]*(t-f+1);
lazy[n] = 0;
}
}
void update(int l, int r, int n, int f, int t, int a) {
propagate(n,l,r);
if (r < f || t < l)return;
if (f <= l && r <= t) {
lazy[n] += a;
return;
}
int mid = (l + r) / 2;
update(l, mid, n * 2, f, t, a);
update(mid + 1, r, n * 2 + 1, f, t, a);
}
int query(int l, int r, int n, int t) {
propagate(n, l,r);
if (t < l || r < t)return 0;
if (l == t && r == t)return seg[n];
int mid = (l + r) / 2;
return query(l, mid, n * 2, t)+ query(mid + 1, r, n * 2 + 1, t);
}
int main(){
FAST;
cin >> N >> M;
REP(i, N) {
int x;
cin >> x;
adj[x].push_back(i);
}
index(1);
while (M--) {
int o, p, s;
cin >> o;
if (o == 1) {
cin >> p >> s; //사람 p 가 s 만큼 손해/이익을 본다
update(1, N, 1, from[p], to[p], s);
}
else {
cin >> p;//사람 p의 잔고 출력
cout <<query(1, N, 1, from[p]) << "\n";
}
}
}
'baekjoon' 카테고리의 다른 글
[백준] 14268 회사 문화 2 (0) | 2023.07.17 |
---|---|
[백준] 2820 자동차 공장 (0) | 2023.07.13 |
[백준] 16395 파스칼의 삼각형 (0) | 2023.07.12 |
[백준] 15458 Barn Painting (0) | 2023.07.12 |
[백준] 12978 스크루지 민호 2 (0) | 2023.07.11 |