(14288) 회사 문화 4

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

단계별로 풀어보기

52단계(세그먼트 트리 2) 3번째

 

 

 

회사 문화 2와 회사 문화 3을 합친 문제인데, 각각의 쿼리는 적용 방식이 다르기 때문에 세그먼트 트리 하나로 관리하면 값이 오염된다(2를 누적합이 아닌 느린 갱신으로 구현했어도 마찬가지). 따라서 각각을 구현한 트리 두 개를 관리해야 한다.

 

 

 

(정답 사진 업로드 깜빡함)

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, cnt;
  
  cin >> n >> m >> cnt; // cnt는 사장 상사 입력 -1 처리용
  
  vector<int> in(n+1), out(n+1);
  vector<vector<int>> adj(n+1);
  
  for(int i=2;i<=n;i++){
    int x;
    
    cin >> x;
    
    adj[x].push_back(i);
  }
  
  auto dfs= [&](auto self, int now, int prev) -> void {
    in[now]= ++cnt;
    
    for(int next:adj[now]){
      if(next==prev)  continue;
      
      self(self, next, now);
    }
    
    out[now]= cnt;
  };
  
  cnt= 0;
  dfs(dfs, 1, 0);
  
  int treesize= (1<<(((int)ceil(log2(n)))+1));
  vector<long> v(n+1), downtree(treesize), uptree(treesize);
  
  auto update= [&](auto self, vector<long> &segtree, int s, int e, int node, int idx, long val) -> void {
    if(idx<s||e<idx)  return;
    
    if(s==e){
      segtree[node]+= val;
    }else{
      self(self, segtree, s, s+(e-s)/2, node*2, idx, val);
      self(self, segtree, s+(e-s)/2+1, e, node*2+1, idx, val);
      segtree[node]= segtree[node*2]+segtree[node*2+1];
    }
  };
  
  auto query= [&](auto self, vector<long> &segtree, int s, int e, int node, int l, int r) -> long {
    if(r<s||e<l)  return 0;
    
    if(l<=s&&e<=r){
      return segtree[node];
    }else{
      long lsum= self(self, segtree, s, s+(e-s)/2, node*2, l, r);
      long rsum= self(self, segtree, s+(e-s)/2+1, e, node*2+1, l, r);
      return lsum+rsum;
    }
  };
  
  bool flag= true;
  
  while(m--){
    int q;
    
    cin >> q;
    
    if(q==1){
      int i, w;
      
      cin >> i >> w;
      
      if(flag){
        update(update, downtree, 1, n, 1, in[i], w);
        if(out[i]+1<=n)  update(update, downtree, 1, n, 1, out[i]+1, -w);
      }else{
        update(update, uptree, 1, n, 1, in[i], w);
      }
    }else if(q==2){
      int i;
      
      cin >> i;
      
      int d= query(query, downtree, 1, n, 1, 1, in[i]);
      int u= query(query, uptree, 1, n, 1, in[i], out[i]);
      
      cout << u+d << "\n";
    }else{
      flag^= 1;
    }
  }
  
  return 0;
}