Submission

Score: 100

User: Pianist

Problemset: เปิดไฟ

Language: cpp

Time: 0.144 second

Submitted On: 2024-11-07 21:46:34

#include <bits/stdc++.h>
using namespace std;
const int MAX = 4e5+1;

int tree[MAX];
bool lazy[MAX];

void toggle(int node, int st, int en, int us, int ue) {
    if (lazy[node]) {
        lazy[node] = false;
        tree[node] = en - st + 1 - tree[node];
        if (st < en) {
            lazy[node << 1] = !lazy[node << 1];
            lazy[1 + (node << 1)] = !lazy[1 + (node << 1)];
        }
    }
    if (st > en || us > en || ue < st)
        return;
    if (us <= st && en <= ue) {
        tree[node] = en - st + 1 - tree[node];
        if (st < en) {
            lazy[node << 1] = !lazy[node << 1];
            lazy[1 + (node << 1)] = !lazy[1 + (node << 1)];
        }
        return;
    }
    int mid = (st + en) / 2;
    toggle((node << 1), st, mid, us, ue);
    toggle((node << 1) + 1, mid + 1, en, us, ue);
    if (st < en)
        tree[node] = tree[node << 1] + tree[(node << 1) + 1];
}

int countQuery(int node, int st, int en, int qs, int qe) {
    if (st > en || qs > en || qe < st)
        return 0;
    if (lazy[node]) {
        lazy[node] = false;
        tree[node] = en - st + 1 - tree[node];
        if (st < en) {
            lazy[node << 1] = !lazy[node << 1];
            lazy[(node << 1) + 1] = !lazy[(node << 1) + 1];
        }
    }
    if (qs <= st && en <= qe)
        return tree[node];
    int mid = (st + en) / 2;
    return countQuery((node << 1), st, mid, qs, qe) +
           countQuery((node << 1) + 1, mid + 1, en, qs, qe);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    int q;
    cin >> q;
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        --l, --r;
        if (op) {
            cout << countQuery(1, 0, n - 1, l, r) << endl;
        } else {
            toggle(1, 0, n - 1, l, r);
        }
    }
    return 0;
}