(1395) 스위치

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

단계별로 풀어보기

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

 

 

 

갱신 쿼리는 구간의 모든 값을 각각 1과 XOR하는 것이고, 출력 쿼리는 구간합을 구하는 것이다. 출력 쿼리는 일반적인 구간합 세그먼트 트리처럼 하면 되고 갱신 쿼리에서 구간을 갱신하는 경우 모든 1은 0으로, 0은 1로 바뀌므로 (구간 길이-원래 구간합)이 갱신된 새로운 값이 된다.

 

 

 

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