이번엔 오일러 경로 테크닉(Euler Tour Technique) 문제를 풀어보게 되었다.
기본적인 오일러 경로 테크닉의 개념은 트리의 각 노드의 진입 시점과 탈출 시점을 DFS를 이용해 기록하여 구간으로 만들고, 세그먼트 트리나 펜윅 트리 등의 자료구조를 이용할 수 있도록 하는 기법.
정확한 동작에 대해선 확실히 이해를 못 해서...
다른 블로그 같은 곳을 참고하는게 나을 것이다.
아래 코드는 백준 2820번 자동차 공장을 오일러 경로 테크닉과 느리게 갱신되는 세그먼트 트리를 이용해 푼 코드.
#include <iostream>
#include <vector>
using namespace std;
int N, M;
int tree[2000001], lazy[2000001], ss[500001], ee[500001], pay[500001], cnt, boss, a;
vector<int> vertex[500001];
string opr;
void propa(int node, int s, int e) {//lazy propagation
if (lazy[node] == 0) { return; }
tree[node] += (e - s + 1) * lazy[node];
if (s != e) {
for (int i = node << 1; i <= (node << 1) + 1; i++) {
lazy[i] += lazy[node];
}
}
lazy[node] = 0;
}
void update(int node, int s, int e, int l, int r, int val) {//업데이트 쿼리
propa(node, s, e);
if (e < l || r < s) { return; }
if (l <= s && e <= r) {
lazy[node] = val;
propa(node, s, e);
return;
}
int mid = s + e >> 1;
update(node << 1, s, mid, l, r, val); update((node << 1) + 1, mid + 1, e, l, r, val);
tree[node] = tree[node << 1] + tree[(node << 1) + 1];
}
int sum(int node, int s, int e, int l, int r) {//구간 합
propa(node, s, e);
if (e < l || r < s) return 0;
if (l <= s && e <= r) return tree[node];
int mid = s + e >> 1;
return sum(node << 1, s, mid, l, r) + sum((node << 1) + 1, mid + 1, e, l, r);
}
void dfs(int x)//오일러 경로 테크닉을 통한 전처리
{
ss[x] = ++cnt;
for (int next : vertex[x]) dfs(next);
ee[x] = cnt;
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> M;
cin >> pay[1];
for (int i = 2; i <= N; i++) {
cin >> pay[i] >> boss;
vertex[boss].push_back(i);
}
dfs(1);
while (M--) {
cin >> opr >> a;
if (opr == "p") {
int x;
cin >> x;
pay[a] -= x;
update(1, 1, cnt, ss[a], ee[a], x);
}
else cout << pay[a] + sum(1, 1, cnt, ss[a], ss[a]) << "\n";
}
}
일단 이건 적당히 따라하고 해서 풀긴 했지만, 다른 문제는 아직까지 접근할 감이 제대로 안 오는 편.
갈 길이 멀다.