[1395] 스위치

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

세그먼트 트리 lazy전파 유형입니다.

N만 작으면 비트마스크로 해결할 수 있을 것이라 생각했는데..

N도 너무 크고.. 흠.. 잘생각이 나지않았습니다.

스위치의 상태를 체크하려면 항상 그 범위만큼의 시간이 필요합니다.

하지만 lazy를 사용하면 해당 범위의 아래 부분은 나중에 업데이트를 하면 됩니다.

그리고 해당 범위의 노드에서 스위치 개수를 뒤집는 방법은

tree[node] = end - start + 1 - tree[node];

이용하면 됩니다.

범위의 개수에서 현재 on개수를 빼면 off개수가 나오기 때문이죠!

아래는 코드입니다.

#include <iostream>
#include <vector>
#include <cmath>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<int, int> vii;
typedef vector<ll, ll> vll;
 
 
void update_lazy(vi &tree, vi &lazy, int node, int start, int end) {
    if (lazy[node]) {
        tree[node] = end - start + 1 - tree[node];
 
        if (start != end) {
            lazy[node * 2] = !lazy[node * 2];
            lazy[node * 2 + 1] = !lazy[node * 2 + 1];
        }
 
        lazy[node] = 0;
    }
}
 
int update_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) {
        return tree[node];
    }
    else if (left <= start && end <= right) {
        tree[node] = end - start + 1 - tree[node];
 
        if (start != end) {
            lazy[node * 2] = !lazy[node * 2];
            lazy[node * 2 + 1] = !lazy[node * 2 + 1];
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int sum_query(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) {
        return 0;
    }
    else if (left <= start && end <= right) {
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return sum_query(tree, lazy, node * 2, start, mid, left, right) + sum_query(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    int tree_size = ceil(log2(n)) + 1;
    vi st(1 << tree_size);
    vi lazy(1 << tree_size);
 
    for (int i = 0, cmd, a, b; i < m; i++) {
        cin >> cmd >> a >> b;
 
        if (cmd) {
            cout << sum_query(st, lazy, 1, 1, n, a, b) << '\n';
        }
        else {
            update_range(st, lazy, 1, 1, n, a, b);
        }
    }
 
    return 0;
}