BOJ 1395 스위치

1시간 31분 3초
보자마자 느리게 갱신되는 트리임을 알았지만 구현력이 딸려서 오래 걸렸다.
lazy를 검사하고 갱신하는 코드를 매 노드에 접근할 때마다 했어야 했다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define x first
#define y second
#define all(v) (v).begin(), (v).end()

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

using pib = pair<int, bool>;
#define value first
#define lazy second

class segment {
public:
    vector<pib> tree; //tree[node] := a[start ~ end] 의 합

    segment() {}
    segment(int size) {
        this->resize(size);
    }
    void resize(int size) {
        size = (int) floor(log2(size)) + 2;
        size = pow(2, size);
        tree.resize(size, pib(0,0));
    }
    void checkLazy(int node, int start, int end) {
        if(tree[node].lazy) {
            tree[node].value = (end-start+1) - tree[node].value;
            tree[node].lazy = false;
            if(start != end) {
                tree[2*node].lazy = !tree[2*node].lazy;
                tree[2*node+1].lazy = !tree[2*node+1].lazy;
            }
        }
    }
    int sum(int node, int start, int end, int left, int right) {
        checkLazy(node, start, end);
        if(right < start || end < left) return 0;
        if(left <= start && end <= right) return tree[node].value;
        return sum(node * 2, start, (start + end) / 2, left, right) +
               sum(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }
    int update(int node, int start, int end, int left, int right) {
        checkLazy(node,start,end);
        if(right < start || end < left) return tree[node].value;
        if(left <= start && end <= right) {
            tree[node].lazy = !tree[node].lazy;
            checkLazy(node, start, end);
            return tree[node].value;
        }
        return tree[node].value =
                       update(node * 2, start, (start + end) / 2, left, right) +
                       update(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }
};

int N, M;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> M;
    segment root(N);
    while(M--) {
        int O, S, T; cin >> O >> S >> T;
        if(O == 0) {
            root.update(1,1,N,S,T);

        }
        else cout << root.sum(1,1,N,S,T) << '\n';
    }


    return 0;
}