BOJ 14288(회사 문화 4)풀이

solved.ac 티어 : 플래 3

www.acmicpc.net/problem/14288

14288번: 회사 문화 4

 

이 문제는 회사 문화 2, 회사 문화 3를3을 합친 문제인데 회사 문화 2를 저장하는 트리와 회사 문화 3을 저장하는 트리를 만들고 각각 업데이트를 해준 뒤 출력할 때 회사 문화 2의 출력 값+회사 문화 3의 출력 값을 해주면 된다.

BOJ 14268(회사 문화 2)풀이

 

BOJ 14287(회사 문화 3)풀이

#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);
vector<ll>ntree(4000000);
vector<ll>ntree1(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){
    ntree[n]=0;
    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(vector<ll>&segtree,vector<ll>&lazytree,ll n,ll s,ll e){
    if(lazytree[n]!=0){
        if(s!=e){
            lazytree[n*2]+=lazytree[n];
            lazytree[n*2+1]+=lazytree[n];
        }
        segtree[n]+=lazytree[n]*(e-s+1);
        lazytree[n]=0;
    }
}
ll max1(vector<ll>&segtree,vector<ll>&lazytree,ll n,ll s,ll e,ll left,ll right){
    propagate(segtree,lazytree,n,s,e);
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return segtree[n];}
    return max1(segtree,lazytree,n*2,s,(s+e)/2,left,right)+max1(segtree,lazytree,n*2+1,(s+e)/2+1,e,left,right);
}
void change(vector<ll>&segtree,vector<ll>&lazytree,ll n,ll s,ll e,ll s1,ll e1,ll f){
    propagate(segtree,lazytree,n,s,e);
    if(s1<=s&&e<=e1){
        lazytree[n]+=f;
        propagate(segtree,lazytree,n,s,e);
        //if(s!=e){
        //    lazytree[n*2]+=f;
        //    lazytree[n*2+1]+=f;
        //}
        //segtree[n]+=f*(e-s+1);
        return;}
    if(e1<s||s1>e){return;}
    change(segtree,lazytree,n*2,s,(s+e)/2,s1,e1,f);
    change(segtree,lazytree,n*2+1,(s+e)/2+1,e,s1,e1,f);
    segtree[n]=segtree[n*2]+segtree[n*2+1];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    ll q,c,d,ce=0,fr,se;
    for(int i = 1; i <= n; i++){
        cin >> p;
        if(p!=-1){graph[p].push_back(i);}
    }
    DFS(1, 0);
    seg(1,1,n);
    //for(int i=1;i<=n;i++){
    //    cout << Qu[i].first << ' ' << Qu[i].second << '\n';
    //}
    for(int i=0;i<m;i++){
        cin >> q;
        if(q==1){
            cin >> c >> d;
            if(ce%2==0)change(tree,tree1,1,1,n,Qu[c].first,Qu[c].second,d);
            else change(ntree,ntree1,1,1,n,Qu[c].first,Qu[c].first,d);
        }else{
            if(q==2){
                cin >> c;
                fr=max1(tree,tree1,1,1,n,Qu[c].first,Qu[c].first);
                se=max1(ntree,ntree1,1,1,n,Qu[c].first,Qu[c].second);
                cout << fr+se << '\n';
                //cout << '3' << '\n';
            }else{ce++;}
        }
    }
}