BOJ 14268(회사 문화 2)풀이

solved.ac 티어 : 플래티넘 3

www.acmicpc.net/problem/14268

14268번: 회사 문화 2

회사 문화 1과 같은 문제인데 1은 마지막에 모든 정점마다 합을 구해주는 거고 2는 2가 들어올 때마다 구간의 합을 구해주는 것이다.

BOJ 14267(회사 문화 1)풀이

#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].second,d);
        }else{
            cin >> c;
            cout << max1(1,1,n,Qu[c].first,Qu[c].first) << '\n';
        }
    }
}