(12844) XOR

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

단계별로 풀어보기

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

 

 

 

느린 갱신을 할 때는 문제에서 주어지는 쿼리에 따라 구간 업데이트를 하는 코드를 어떻게 짜는지가 중요하다. 이전 문제에서는 출력 쿼리가 구간의 합이었으므로 구간 갱신을 할 때 입력값에 구간 길이를 곱한 값을 더해줬는데, 이 문제는 구간에 XOR한 것이 출력 쿼리이므로 구간 길이가 홀수일 때만 입력값을 XOR해준다. 짝수라면 해당 구간에 적용된 XOR은 나중에 XOR할 때 영향을 미치지 않기 때문이다.

 

 

 

#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;
  
  cin >> n;
  
  int treesize= (1<<(((int)ceil(log2(n)))+1));
  vector<long> v(n+1), segtree(treesize), lazy(treesize);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  auto init= [&](auto self, int s, int e, int node) -> void {
    if(s==e){
      segtree[node]= v[s];
    }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]){
      if((e-s+1)&1)  segtree[node]^= lazy[node];
      
      if(s!=e){
        lazy[node*2]^= lazy[node];
        lazy[node*2+1]^= lazy[node];
      }
      
      lazy[node]= 0;
    }
  };
  
  auto update= [&](auto self, int s, int e, int node, int l, int r, long val) -> void {
    updatelazy(s, e, node);
    
    if(r<s||e<l)  return;
    
    if(l<=s&&e<=r){
      if((e-s+1)&1)  segtree[node]^= 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(r<s||e<l)  return 0;
    
    if(l<=s&&e<=r){
      return segtree[node];
    }else{
      long lres= self(self, s, s+(e-s)/2, node*2, l, r);
      long rres= self(self, s+(e-s)/2+1, e, node*2+1, l, r);
      return lres^rres;
    }
  };
  
  init(init, 1, n, 1);
  
  cin >> m;
  
  while(m--){
    int q;
    
    cin >> q;
    
    if(q==1){
      int i, j, k;
      
      cin >> i >> j >> k;
      
      update(update, 1, n, 1, i+1, j+1, k);
    }else{
      int i, j;
      
      cin >> i >> j;
      
      cout << query(query, 1, n, 1, i+1, j+1) << "\n";
    }
  }
  
  return 0;
}