백준 2820번: 자동차 공장 (C++)

https://www.acmicpc.net/problem/2820

2820번: 자동차 공장

---

Solved By: Euler Tour Technique, Segment Tree, Lazy Propagation

 

상사와 부하의 관계는 트리 구조로 나타낼 수 있으며 업데이트마다 DFS를 사용하기엔 N, M의 범위가 커서 시간 초과가 걸릴 가능성이 큽니다. Euler Tour Technique을 사용하여 트리를 Segment Tree처럼 만들어서 구간별로 업데이트한다면 시간을 확실하게 줄일 수 있습니다.

 

또한, 이때의 update는 구간을 update 해야 하는데 보통의 세그먼트 트리에서 구간을 업데이트하면 O(nlogn)이 걸리므로 시간 초과가 납니다. 이를 위해 Lazy Propagation까지 사용합니다.

>> 구간 업데이트 O(logn)

 

#include <iostream>
#include <vector>
#include <utility>
#define MAX (500000 + 1)
#define pii pair<int, int>
#define ll long long
using namespace std;

int n, m;
vector<int> adj[MAX];
pii ett[MAX];
ll money[MAX];
ll sgTree[MAX * 4];
ll lazy[MAX * 4];
vector<ll> result;

int dfsN = 0;
void dfs(int now, int par){
    ett[now].first = ++dfsN;
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        if(next == par) continue;
        dfs(next, par);
    }
    
    ett[now].second = dfsN;
}

void lazyUpdate(int start, int end, int node){
    if(!lazy[node]) return;
    
    sgTree[node] += lazy[node];
    if(start != end) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    
    lazy[node] = 0;
}

void update(int start, int end, int node, int left, int right, ll val){
    lazyUpdate(start, end, node);
    if(end < left || start > right) return;
    if(left <= start && end <= right){
        if(start == end){
            sgTree[node] += val;
        }
        else{
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    }
    
    int mid = (start + end) >> 1;
    update(start, mid, node * 2, left, right, val);
    update(mid + 1, end, node * 2 + 1, left, right, val);
}


ll query(int start, int end, int node, int idx){
    lazyUpdate(start, end, node);
    if(idx < start || end < idx) return 0;
    if(start == end) return sgTree[node];
    
    int mid = (start + end) >> 1;
    return query(start, mid, node * 2, idx) 
    + query(mid + 1, end, node * 2 + 1, idx);
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> money[i];
        if(i == 1) continue;
        int v; cin >> v;
        adj[v].push_back(i);
    }
    
    dfs(1, 0);
    
    for(int i = 1; i <= n; i++){
        update(1, n, 1, ett[i].first, ett[i].first, money[i]);
    }
    
    /*
    // Euler Tour Technique Check
    for(int i = 1; i <= n; i++){
        cout << ett[i].first << ' ' << ett[i].second << '\n';
    }
    */
    
    for(int i = 0; i < m; i++){
        char q;
        cin >> q;
        if(q == 'p'){
            int a, w;
            cin >> a >> w;
            update(1, n, 1, ett[a].first + 1, ett[a].second, w);
            // 자신을 제외한 부하들의 월급이기 때문에
            // ett[a].first에다가 +1을 해준다.
        }
        else{
            int a;
            cin >> a;
            result.push_back(query(1, n, 1, ett[a].first));
        }
    }
    
    for(int i = 0; i < result.size(); i++){
        cout << result[i] << '\n';
    }
    return 0;
}