BOJ 14287(회사 문화 3)풀이

solved.ac 티어 : 플래티넘 4

www.acmicpc.net/problem/14287

14287번: 회사 문화 3

이 문제는 다른 회사 문화 문제와는 다르게 위에서 아래로 값을 더해주는 것이 아닌 밑에서 위로 값을 더해주는 문제이다.

이 문제의 풀이는 생각보다 간단하다. dfs으로 새로 해당 구간을 만들고 그 구간에 대한 이진트리를 그리고 x노드의 값에 w를 더한다고 해보자.

그러면 x를 가지고 있는 구간에만 변경이 생긴다. 그러므로 구간이 (x,x)인 위치에 w를 더해주면 x를 포함하고 있는 구간에는 더해지지만 x를 포함하고 있지 않은 구간에는 더해지지 않는다. 

그리고 출력은 x노드의 구간의 합을 구해주면 된다. w는 x를 포함하고 있는 구간에만 더해지기 때문에 x노드의 구간합을 구해주면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> nod;
const ll N=1000000;
ll n,m;
vector<ll> graph[N];
nod Qu[N]; 
ll cnf=0,p;
vector<ll>tree(4000000);
vector<ll>tree1(4000000);
void DFS(ll v,ll p){
    Qu[v].first = ++cnf;
    for(ll nv : graph[v]){
        if (nv==p){continue;}
        DFS(nv,v);
    }
    Qu[v].second=cnf;
}
ll seg(ll n,ll s,ll e){
    if(s==e){return tree[n]=0;}
    return tree[n]=seg(n*2,s,(s+e)/2)+seg(n*2+1,(s+e)/2+1,e);
}
void propagate(ll n,ll s,ll e){
    if(tree1[n]!=0){
        if(s!=e){
            tree1[n*2]+=tree1[n];
            tree1[n*2+1]+=tree1[n];
        }
        tree[n]+=tree1[n]*(e-s+1);
        tree1[n]=0;
    }
}
ll max1(ll n,ll s,ll e,ll left,ll right){
    propagate(n,s,e);
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return tree[n];}
    return max1(n*2,s,(s+e)/2,left,right)+max1(n*2+1,(s+e)/2+1,e,left,right);
}
void change(ll n,ll s,ll e,ll s1,ll e1,ll f){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){tree1[n]+=f;propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1,f);
    change(n*2+1,(s+e)/2+1,e,s1,e1,f);
    tree[n]=tree[n*2]+tree[n*2+1];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    ll q,c,d;
    for(int i = 1; i <= n; i++){
        cin >> p;
        if(p!=-1){graph[p].push_back(i);}
    }
    DFS(1, 0);
    //for(int i=1;i<=n;i++){
    //    cout << Qu[i].first << ' ' << Qu[i].second <<'\n';
    //}
    seg(1,1,n);
    for(int i=0;i<m;i++){
        cin >> q;
        if(q==1){
            cin >> c >> d;
            change(1,1,n,Qu[c].first,Qu[c].first,d);
        }else{
            cin >> c;
            cout << max1(1,1,n,Qu[c].first,Qu[c].second) << '\n';
        }
    }
}