(18437) 회사 문화 5

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

단계별로 풀어보기

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

 

 

 

갱신 쿼리는 자신을 제외한 모든 서브트리에 적용되므로 오일러 경로 테크닉을 쓰면 된다. 오일러 경로 구간의 왼쪽 값은 자기 자신을 의미하므로 [l+1,r]의 구간을 갱신하면 된다.

일반적인 세그먼트 트리로 생각하면 갱신 쿼리는 구간 내 모든 값을 0이나 1로 바꾸는 것이고, 출력 쿼리는 구간합을 구하는 것이다. 어려운 점은 없지만 이 문제에서는 어떤 구간이 나타내는 lazy배열의 값이 0인 경우에도 갱신이 필요하기 때문에 lazy를 다시 원래 세그먼트 트리로 갱신하는 부분을 잘 설정해야 한다.

 

 

 

#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 >> cnt; // cnt는 사장 상사 입력 0 처리용
  
  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), segtree(treesize), lazy(treesize, -1);
  
  auto init= [&](auto self, int s, int e, int node) -> void {
    if(s==e){
      segtree[node]= 1;
    }else{
      self(self, s, s+(e-s)/2, node*2);
      self(self, s+(e-s)/2+1, e, node*2+1);
      segtree[node]= segtree[node*2]+segtree[node*2+1];
    }
  };
  
  auto updatelazy= [&](int s, int e, int node) -> void {
    if(lazy[node]!=-1){
      segtree[node]= (e-s+1)*lazy[node];
      
      if(s!=e){
        lazy[node*2]= lazy[node];
        lazy[node*2+1]= lazy[node];
      }
      
      lazy[node]= -1;
    }
  };
  
  auto update= [&](auto self, int s, int e, int node, int l, int r, long val) -> void {
    updatelazy(s, e, node);
    
    if(l>r||r<s||e<l)  return;
    
    if(l<=s&&e<=r){
      segtree[node]= (e-s+1)*val;
      
      if(s!=e){
        lazy[node*2]= val;
        lazy[node*2+1]= val;
      }
    }else{
      self(self, s, s+(e-s)/2, node*2, l, r, val);
      self(self, s+(e-s)/2+1, e, node*2+1, l, r, val);
      segtree[node]= segtree[node*2]+segtree[node*2+1];
    }
  };
  
  auto query= [&](auto self, int s, int e, int node, int l, int r) -> long {
    updatelazy(s, e, node);
    
    if(l>r||r<s||e<l)  return 0;
    
    if(l<=s&&e<=r){
      return segtree[node];
    }else{
      long lsum= self(self, s, s+(e-s)/2, node*2, l, r);
      long rsum= self(self, s+(e-s)/2+1, e, node*2+1, l, r);
      return lsum+rsum;
    }
  };
  
  init(init, 1, n, 1);
  
  cin >> m;
  
  while(m--){
    int q, i;
    
    cin >> q >> i;
    
    if(q==1){
      update(update, 1, n, 1, in[i]+1, out[i], 1);
    }else if(q==2){
      update(update, 1, n, 1, in[i]+1, out[i], 0);
    }else{
      cout << query(query, 1, n, 1, in[i]+1, out[i]) << "\n";
    }
  }
  
  return 0;
}