백준 1395번 - 스위치

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

1395번: 스위치

# Approach)

선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자.

해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다.

 

# Time Complexity)

업데이트를 진행할때 s~t구간의 스위치를 모두 토글해야한다. 

각 원소를 하나하나 토글한다면 세그먼트 트리를 사용했을때 시간복잡도는최대 한번의 업데이트에 $O(log(n))$으로 전체의 쿼리에 대해 최악의 상황으로 가정한다면 $O(mnlog(n)) > 10^8$ 로 TLE를 받게 될 것이다.

따라서 lazy propagation을 이용하여 각 업데이트를 $O(log(n))$안에 해결해주어야 한다. 

 

 

#Code(c++)

#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define pf first
#define ps second
#define pii pair<int,int> 
#define ll long long
#define lll __int128
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int N = 1 << 17;
int n,m;
int seg[1<<18];
bool lazy[1<<17];
void apply(int idx, int len){
  seg[idx]=len-seg[idx];
  lazy[idx]=0;
  if(len!=2) lazy[idx<<1]^=1,lazy[idx<<1|1]^=1;
  else seg[idx<<1]^=1,seg[idx<<1|1]^=1;
}

void propagate(int idx,int len){
  int logv=0,e=idx; while(e>1)e>>=1,logv++;
  for(int i=logv;i>=0;i--) if(idx>>i<N&&lazy[idx>>i]) apply(idx>>i,len<<i);
}

void query(int l,int r){
  int sum=0,len=1;
  for(l+=N,r+=N;l<r;l>>=1,r>>=1,len<<=1) {
    if(l&1){propagate(l,len);sum+=seg[l++];} 
    if(r&1){propagate(--r, len);sum += seg[r];}
  }
  cout<<sum<<endl;
}

void mark(int idx,int len){
  propagate(idx,len);
  int d=len-(seg[idx]<<1);
  if(idx<N) lazy[idx]^=1;
  else seg[idx]+=d;
  while(idx>1) idx>>=1,seg[idx]+=d;
}

void update(int l,int r){
  int len=1;
  for(l+=N,r+=N;l<r;l>>=1,r>>=1,len<<=1) {
    if(l&1) mark(l++,len);
    if(r&1) mark(--r,len);
  }
}

int main() {
  FASTIO; cin>>n>>m;
  for0(i,m) {
    int o,s,t; cin>>o>>s>>t;
    if(o == 1) query(s,t+1);
    else update(s,t+1);
  }
  return 0;
}