[백준 1395번] [Lazy propagation] 스위치

Approach

구간에 대한 정보를 변경하는 쿼리와 구간에 대한 질의를 하고 있는 쿼리를 보내고 있는 상황이므로, Lazy propagation임은 쉽게 파악할 수 있었을 것이다.

 

그러면, lazy를 어떻게 정의할 것인지를 파악하는 것이 중요할 것이다.

아이디어 자체는 이 문제와 상당히 유사하다.

https://viyoung.tistory.com/399

[백준 12844번] [Lazy propagation] XOR

이 문제도 XOR의 성질을 활용하여 XOR을 2번 처리하면 처리하지 않은 것과 같다는 것을 이용한 문제였는데, 스위치 또한 2번 조작하면 결과적으로 하나도 조작하지 않은 것과 같다는 점에서 완벽하게 동일한 문제라고 할 수 있겠다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
int seg[400000];
int lazy[400000];

void propagate(int node, int start, int end){
    if(lazy[node] % 2 == 1){
        if(start != end){
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        seg[node] = (end - start + 1) - seg[node];
        lazy[node] = 0;
    }
}

void update(int node, int start, int end, int left, int right){
    propagate(node, start, end);
    if(end < left || right < start) return;
    if(left <= start && end <= right){
        lazy[node] += 1;
        propagate(node, start, end);
        return;
    }
    int mid = (start + end) >> 1;
    update(node * 2, start, mid, left, right);
    update(node * 2 + 1, mid + 1, end, left, right);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

int query(int node, int start, int end, int left, int right){
    propagate(node, start, end);
    if(end < left || right < start) return 0;
    if(left <= start && end <= right) return seg[node];
    int mid = (start + end) >> 1;
    return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
\
}

int main() {
    fastio;
    memset(seg, 0, sizeof(seg));
    memset(lazy, 0, sizeof(lazy));
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        if(a == 0){
            update(1, 1, 100000, b, c);
        }
        else{
            cout << query(1, 1, 100000, b, c) << "\n";
        }
    }
    return 0;
}