백준 2820 자동차 공장 혼내주기

 

 

 

내 접근법은 트리를 만들고 월급을 출력해야 할 때 해당 노드부터 root 까지 올라가는 path를 저장하고 그 path의 역순으로 update를 해서 propagated 값을 출력하는 방법이었는데 TLE를 받았다. 시초를 받고 생각해보니 트리가 skewed tree일 때 매번 경로를 찾기 위해 O(N)이 걸리기 때문에 그런 것 같다.

도저히 풀이가 안떠올라서 검색하다가 ANZ님의 블로그를 보고 이해했다. range가 없으니 dfs로 해당 노드의 구간을 만들어서 쿼리를 날린다...
구현하고도 dfs로 재정의된 노드 순서를 적용 안해서 또 한참 헤맸다. 세그 문제들은 디버깅이 어렵다.

결국 lazy에 구간 재정의만 해주면 되는 문제였고, 그걸 검색해서 알고도 왜 이렇게 헤맸을까........
세상에 똑똑한 사람이 넘모 많은데 나는 거기에 속하지 않는게 넘모 슬프다...

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;

const int N = 1<<19;
vector<ll> adj[N];
ll tree[N<<1], lazy[N<<1];
int from[N], to[N], tmp[N];
int n, m;

void input() {
    fastio;
    int a, b;
    cin >> n >> m >> a;
    tmp[0] = a;
    for(int i = 1; i < n; ++i) {
        cin >> a >> b;
        tmp[i] = a;
        adj[b-1].push_back(i);
    }
}

int idx = -1;
void dfs(int u) {
    from[u] = ++idx;
    for(auto& v : adj[u]) {
        dfs(v);
    }
    to[u] = idx;
}

void propagate(int i, int s, int e) {
    if(lazy[i]) {
        if(i < N) {
            lazy[i<<1] += lazy[i];
            lazy[i<<1|1] += lazy[i];
        }
        tree[i] += lazy[i];
        lazy[i] = 0;
    }
}

void update(int l, int r, int x, int i = 1, int s = 0, int e = N-1) {
    propagate(i, s, e);

    if(l > e || r < s) return ;
    if(l <= s && e <= r) {
        
        lazy[i] += x;
        propagate(i, s, e);
        return ;
    }
    int m = (s + e) >> 1;
    update(l ,r, x, i<<1, s, m);
    update(l, r, x, i<<1|1, m+1, e);
}

ll query(int l, int r, int i = 1, int s = 0, int e = N-1) {
    propagate(i, s, e);
    
    if(l > e || r < s) return 0;
    if(l <= s && e <= r) return tree[i];
    int m = (s + e) >> 1;
    return query(l, r, i<<1, s, m) + query(l, r, i<<1|1, m+1, e);
}

int main() {
    input();

    dfs(0);
    for(int i = 0; i < n; ++i) {
        tree[from[i]+N] = tmp[i];
    }
    
    while(m--) {
        char op; cin >> op;
        if(op == 'p') {
            int a, b; cin >> a >> b;
            update(from[a-1]+1, to[a-1], b);
        }
        else {
            int a; cin >> a;
            cout << query(from[a-1], from[a-1]) << "\n";
        }
    }
}