감이 안 오는 오일러 경로 테크닉

SeokguKim·2022년 9월 4일
0

이번엔 오일러 경로 테크닉(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";
    }
}

일단 이건 적당히 따라하고 해서 풀긴 했지만, 다른 문제는 아직까지 접근할 감이 제대로 안 오는 편.

갈 길이 멀다.

profile
좋은 일이 생길거야

0개의 댓글