[백준 1395] 스위치 (C++)

1395번: 스위치

세그먼트 트리

---

오랜만의 백준 풀이다. 어저께 하루 종일 고민하면서 구현했고 방금 구현을 마무리해서 AC를 받았다. 

처음엔 3653 영화 수집 문제를 풀려고 했는데 아무리 생각해도 푸는 방법이 생각이 안 나서 런하고 만난 문제가 이번 문제다. 도망쳐서 만났기 때문에 한번 더 도망칠 수가 없었다..

 

전에 풀었던 구간합구하기2 문제랑 느낌이 비슷해서 레이지 세그먼트 트리로 감을 잡았다.

[백준 10999] 구간 합 구하기 2 (C++)

구간의 모든 전구를 스위칭 한다는게 레이지 세그먼트트리를 공부한 사람은 바로 느낄 수 있는 단서라고 생각한다.

 

트리의 각 노드는 자식 노드들의 켜진 전구수 합, 꺼진 전구수 합을 가지고 있는 pair 자료형을 가지도록 했다.

레이지 트리의 노드는 구간의 스위치를 반전시킨 횟수를 저장하도록 했다.

 

(현재 노드는 구간 정보를 가진다. 따라서 구간==노드)

전구를 반전시킬 때 : 현재 구간이 주어진 쿼리 구간에 포함된다면 현재 구간에 있는 모든 전구를 반전시키므로 구간의 켜진 전구수합과 꺼진 전구수합을 swap해준다. 그리고 전구를 반전시켰으므로 현재 노드의 lazy를 0으로 만들어준다. 처리할 전구가 없다는 뜻이다. 그리고 리프노드가 아니라면 자식노드로 lazy를 전파시켜준다. 자식노드의 반전 횟수를 1 증가시켜 준다.

lazy를 처리하는 함수에서는 반전 횟수가 홀수일 때만 처리한다. 짝수면 당연히 볼 필요가 없다. 홀수면 위에서 말했듯이 구간의 꺼진 전구수, 켜진 전구수를 swap하고 구간의 lazy를 초기화 시키며, 리프노드가 아니면 자식노드로 lazy를 전파한다.

 

켜져있는 스위치의 개수를 반환할 때도 lazy를 처리해주면서 구간을 탐색한다. 이건 구간 합 구할 때와 비슷하게 쉽게 구현이 가능하다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define NUM 100001
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
 
// first : 켜짐  second : 꺼짐
pii tree[NUM * 4];
int lazy[NUM * 4];
 
 
int make_tree(int startidx, int endidx, int node){
    if(startidx == endidx) return tree[node].second = 1;
    int mid = (startidx + endidx) / 2;
    return tree[node].second = make_tree(startidx, mid, node*2) + \
                               make_tree(mid+1, endidx, node*2+1);
}
 
void reverse_lazy(int startidx, int endidx, int node){
    if(lazy[node] % 2){
        swap(tree[node].first, tree[node].second);
        lazy[node] = 0;
        if(startidx != endidx){
            lazy[node*2]++;
            lazy[node*2+1]++;
        }
        return;
    }
}
 
// lidx 스위치부터 ridx 스위치까지 뒤집기
void reverse_query(int startidx, int endidx, int lidx, int ridx, int node){
    reverse_lazy(startidx, endidx, node);
    if(lidx > endidx || ridx < startidx) return;
    if(lidx <= startidx && endidx <= ridx){
        swap(tree[node].first, tree[node].second);
        lazy[node] = 0;
        if(startidx != endidx){
            lazy[node*2]++;
            lazy[node*2+1]++;
        }
        return;
    }
    
    int mid = (startidx + endidx) / 2;
    reverse_query(startidx, mid, lidx, ridx, node*2);
    reverse_query(mid+1, endidx, lidx, ridx, node*2+1);
    tree[node].first = tree[node*2].first + tree[node*2+1].first;
    tree[node].second = tree[node*2].second + tree[node*2+1].second;
}
 
// lidx 스위치부터 ridx 스위치 중에서 켜져있는 스위치의 개수를 반환
int get_query(int startidx, int endidx, int lidx, int ridx, int node){
    reverse_lazy(startidx, endidx, node);
    if(lidx > endidx || ridx < startidx) return 0;
    if(lidx <= startidx && endidx <= ridx) return tree[node].first;
    
    int mid = (startidx + endidx) / 2;
    return get_query(startidx, mid, lidx, ridx, node*2) + \
           get_query(mid+1, endidx, lidx, ridx, node*2+1);
}
 
void solve(){
    make_tree(1, N, 1);
    
    int o, s, t;
    for(int i = 0; i < M; i++){
        cin >> o >> s >> t;
        if(o == 0) reverse_query(1, N, s, t, 1);
        else cout << get_query(1, N, s, t, 1) << "\n";
    }
}
 
int main(){
    fastio
    cin >> N >> M;
    solve();
    
    return 0;
}