카테고리 없음
백준 16404 c++ "주식회사 승범이네" -PlusUltraCode-
PlusUltraCode
2025. 1. 18. 19:39
https://www.acmicpc.net/problem/16404
[필자 사고]
이 문제는 세그먼트 트리 자료구조를 이용해서 풀어야 되는 문제이다.
다만 이 문제만의 재미난 점은 세그먼트 index를 설정해야 되는데 그게 dfs탐색을 이용한 오일러 알고리즘을 통해
index들을 새로 정의 해야 된다.
DFS알고리즘을 잘 수행했따면 Propagation 으로 느린전파 알고리즘을 이용하여 Update의 범위 쿼리를 갱신해주면 문제를 풀 수 있게 된다.
여기서 필자는 1-based로 시작했기 때문에 index[a].first 가 의미하는 거는 a의 실제 index자신을 의미하므로
a보다 부하를 원하면 index[a].first +1 을 해야된다는 점이다.
[코드 해설]
1. 전역 변수 초기화
코드 상단에서 전역 변수들이 선언 및 초기화됩니다. 이들은 세그먼트 트리와 관련된 자료구조와 입력 데이터 저장에 사용됩니다.
- tree: 세그먼트 트리를 저장하는 벡터.
- lazy: Lazy Propagation 값을 저장하는 벡터.
- index: 각 노드의 DFS 방문 순서와 구간을 저장하는 벡터.
- list: 트리의 간선 정보를 저장하는 인접 리스트.
- N, M: 노드 수와 쿼리 수.
- cnt: DFS 방문 순서를 기록하기 위한 변수.
2. 입력 처리 (Input 함수)
Input() 함수는 트리의 구조를 입력받고 인접 리스트 list를 초기화합니다.
- N(노드의 수)와 M(쿼리의 수)를 입력받습니다.
- 세그먼트 트리(tree)와 Lazy Propagation 배열(lazy), 그리고 DFS 정보를 저장할 index, list를 적절히 크기에 맞게 초기화합니다.
- 각 노드의 부모 정보를 입력받아 트리 구조를 인접 리스트 형태로 구성합니다.
- 부모가 -1이면 루트 노드로 간주하고, 자식 노드를 list[idx]에 추가합니다.
3. DFS를 통한 노드 구간 설정 (Dfs 함수)
Dfs() 함수는 트리를 순회하며 각 노드의 DFS 방문 순서와 구간 범위를 계산합니다.
- 노드를 방문할 때, 방문 순서를 기록하고 index[num].first에 저장합니다.
- 현재 노드의 모든 자식 노드를 재귀적으로 방문합니다.
- 방문이 끝난 후, 해당 노드의 구간 종료 시점을 index[num].second에 저장합니다.
4. Lazy Propagation 적용 (Propagation 함수)
Propagation() 함수는 Lazy Propagation을 적용하여 필요할 때 계산을 연기한 값을 처리합니다.
- lazy[node]가 0이 아니면:
- 현재 구간에 저장된 값을 업데이트하고, 자식 노드에 lazy 값을 전달합니다.
- 리프 노드가 아니면, 자식 노드에 lazy 값을 저장해 두고 현재 노드의 lazy 값을 초기화합니다.
5. 구간 업데이트 (Update 함수)
Update() 함수는 주어진 구간 [left, right]에 대해 특정 값을 더하는 작업을 수행합니다.
- Propagation()을 호출하여 필요한 업데이트를 적용합니다.
- 현재 구간이 업데이트 범위와 겹치지 않으면 종료합니다.
- 현재 구간이 완전히 업데이트 범위에 포함되면:
- lazy[node]에 값을 추가하고, Propagation()을 호출해 즉시 적용합니다.
- 범위가 겹치는 경우:
- 중간 지점(mid)을 기준으로 좌우 자식 노드를 재귀적으로 호출합니다.
- 두 자식의 결과를 합산해 현재 노드 값을 갱신합니다.
6. 구간 조회 (Query 함수)
Query() 함수는 특정 인덱스의 값을 출력합니다.
- Propagation()을 호출하여 필요한 업데이트를 적용합니다.
- 인덱스가 현재 구간에 포함되지 않으면 종료합니다.
- 현재 노드가 리프 노드일 경우, 해당 값을 출력합니다.
- 리프 노드가 아니라면:
- 중간 지점(mid)을 기준으로 좌우 자식 중 해당 인덱스를 포함하는 구간으로 이동합니다.
7. 쿼리 실행 (Game_Start 함수)
Game_Start() 함수는 주어진 쿼리를 처리하는 메인 함수입니다.
- Dfs()를 호출하여 각 노드의 DFS 방문 순서와 구간 정보를 설정합니다.
- 사용자로부터 입력받은 M개의 쿼리를 처리합니다:
- flag == 1: 특정 노드와 그 하위 노드들에 값을 더합니다. (Update() 호출)
- flag == 2: 특정 노드의 값을 출력합니다. (Query() 호출)
[소스 코드]
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
vector<ll> tree;
vector<ll> lazy;
vector<pair<int, int>> index;
vector<vector<int>> list;
int N, M , cnt = 0;
void Input() {
cin >> N >> M;
tree.resize(N*4);
lazy.resize(N*4);
index.resize(N + 1);
list.resize(N + 1);
for (int i = 1; i <= N; i++) {
ll idx;
cin >> idx;
if (idx == -1)continue;
list[idx].push_back(i);
}
}
void Dfs(int num) {
index[num].first = ++cnt;
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 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);
for (int i = 0; i < M; i++) {
int flag;
cin >> flag;
if (flag == 1) {
ll a, b;
cin >> a >> b;
Update(1, 1, N, index[a].first, index[a].second, b);
}
else {
ll 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();
}