[백준] No.1395 - 스위치 (C++, Segment Tree Lazy Propagation)

문제

 

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

1395번: 스위치

 

풀이

 

solved.ac 난이도: Platium 3

 

세그먼트 트리에서 특정 구간의 값들이 자주 변경되어야 할 때 사용되는 Segment Tree Lazy Propagation(느리게 갱신되는 세그먼트 트리) 문제이다.

Segment Tree Lazy Propagation에 대해서는 깔끔히 설명해주신 백준님의 게시글을 보고 오자.

세그먼트 트리 나중에 업데이트 해야지! - Baekjoon Online Judge

세그먼트 트리 나중에 업데이트 해야지!

 

일반적인 세그먼트 트리의 구현에서는 Update되는 값은 한 가지 원소만이 존재했지만

위의 게시글에서 소개하는 문제는 구간의 모든 원소들의 값을 변경해주어야 한다.

기존의 세그먼트 트리로는 Update를 반복 호출하여야만 하기 때문에 굉장히 비효율적이다.

 

 

Segment Tree Lazy Propagation에서는 트리에서의 노드가 계산이 필요할 때까지 최대한 처리를 늦춘다.(프로그래밍 분야에서 lazy는 계산이 필요할 때까지 최대한 처리를 늦추는 방식을 의미)

나중에 해당 구간의 노드를 방문하게 되면 미루었던 값의 Update를 진행하기 때문에 구간의 범위에 포함되는 모든 하위 노드들을 불필요하게 방문할 필요가 없어진다.

 

 

 

 

다시 이번 문제로 돌아오자.

이번 문제는 간단히 구간의 변경과 합을 물어보는 문제가 아니다.

구간의 스위치들의 상태를 반전시키고 구간에서 켜져 있는 스위치를 계산하는 문제이다.

 

일단 세그먼트 트리의 각 노드(segment_tree[node])에는 해당 노드가 담당하는 구간의 켜진 스위치의 개수를 저장한다고 하자.

그렇다면 구간의 스위치 상태 반전은 어떻게 구현할까?

 

노드(node)가 담당하는 구간이 [left, right]라고 하자.

기존에 [left, right]구간에 켜진 스위치의 개수는 segment_tree[node]에 저장되어 있다.

해당 구간이 반전된다면 켜진 스위치는 꺼지고 꺼진 스위치는 켜진다.

따라서 꺼진 스위치의 개수가 반전된 구간의 켜진 스위치의 개수가 된다.

이는 (현재 꺼진 스위치의 개수) = (구간의 전체 스위치의 개수) - (현재 켜진 스위치의 개수)

segment_tree[node] = (right - left +1) - segment_tree[node]

 

구간이 합을 구하는 경우 lazy[node]에는 node 구간에 더해저야할 수 가 저장되어 있었다.

이번 문제에서는 lazy[node]에 node 구간의 스위치 반전 횟수를 저장한다.

그런데 사실 같은 구간의 스위치들을 두 번 반전하면 결국 원래 상태로 돌아온다.

따라서 lazy[node](반전 횟수)는 홀수일 때만 의미가 있다.

그러므로 해당 문제의 lazy를 반영하는 함수는 아래와 같이 구현해준다.

 

void UpdateLazy(int left, int right, int node){
  if(lazy[node] %2 == 1){ //홀수일때만 의미가 있다.
    segment_tree[node] = (right - left +1) - segment_tree[node];
    if(left != right){
      lazy[node*2] += lazy[node];
      lazy[node*2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
}

 

구간의 스위치를 반전하는 함수

void UpdateRange(int left, int right, int range_left, int range_right, int node)

는 방문하는 노드들마다 UpdateLazy( )를 호출하여 해당 노드의 lazy가 홀수라면 반영해주자.

 

 

void UpdateRange(int left, int right, int range_left, int range_right, int node){
  UpdateLazy(left, right,node);
  if(range_right < left || right < range_left)
    return;
  
  if(range_left <= left && right<= range_right){
    segment_tree[node] = (right - left +1) - segment_tree[node];
    if(left != right){
      lazy[node*2] += 1;
      lazy[node*2 + 1] += 1;
    }
    return;
  }
 
  int mid = (left + right)/2;
  UpdateRange(left, mid , range_left ,range_right  , node*2 );
  UpdateRange(mid+1, right , range_left ,range_right  , node*2+1 );
 
  segment_tree[node] = segment_tree[node*2] + segment_tree[node*2+1];
  return;
}

 

 

최종적으로 질의 구간의 켜진 스위치 개수를 반환하는 함수는 아래와 같다.

 

int SumOnSwitch(int left, int right, int range_left, int range_right, int node){
  UpdateLazy(left, right,node);
  if(range_right < left || right < range_left)
    return 0;
 
  if(range_left <= left && right<= range_right)
    return segment_tree[node];
 
  int mid = (left + right)/2;
  return SumOnSwitch(left, mid , range_left ,range_right  , node*2) + SumOnSwitch(mid+1, right , range_left ,range_right  ,node*2+1);
}

 

 

 

코드