백준 1395번 - 스위치

On this page

BOJ 1395 — Switches

Problem

There are $N$ switches, all initially off. Each operation gives a range $[S,T]$ with $1\le S\le T\le N$:

• 0 S T: toggle every switch in the inclusive range $[S,T]$.
• 1 S T: print the number of switches that are on in the inclusive range $[S,T]$.

Toggling means changing each off switch to on and each on switch to off. The ranges and the C++ implementation below are one-based and inclusive.

Segment tree and lazy toggles

Build a recursive segment tree over positions $1$ through $N$. Each node stores the number of on switches in its segment. A second value, a lazy XOR toggle bit, records whether a toggle has already been applied to that whole segment but has not yet been passed to its children.

If a segment has length $L$ and currently contains on on switches, toggling the whole segment changes the count to

$$L-\text{on}.$$

The lazy bit is XORed with 1 at the same time. A second toggle therefore restores the original count and clears the pending bit: two toggles cancel.

Before descending into children for a partial update or query, push applies the pending toggle to both children. For each child it uses that child’s segment length to replace its count with length - on, and XORs its lazy bit. It then clears the parent’s bit. A leaf has no children to update.

For a range update, a disjoint segment needs no work. If a node’s segment is fully covered by the requested range, apply one toggle to the node and stop descending. Otherwise, push its pending toggle, recurse into both children, and recompute the node’s count as the sum of the children’s counts.

For a range query, a disjoint segment contributes 0, and a fully covered segment contributes its stored count. For a partial overlap, push before recursing and add the two child results. With inclusive endpoints, a segment $[left,right]$ is disjoint from $[ql,qr]$ exactly when qr < left || right < ql; it is fully covered when ql <= left && right <= qr.

At each level only a constant number of segment-tree nodes are visited, so each update and query takes $O(\\log N)$ time. The tree and lazy arrays each use $O(N)$ storage.

C++17 implementation

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
    int n;
    vector<int> on;
    vector<bool> lazy;

    void apply(int node, int left, int right) {
        on[node] = (right - left + 1) - on[node];
        lazy[node] = !lazy[node];
    }

    void push(int node, int left, int right) {
        if (!lazy[node] || left == right) return;
        int mid = left + (right - left) / 2;
        apply(node * 2, left, mid);
        apply(node * 2 + 1, mid + 1, right);
        lazy[node] = false;
    }

    void toggle(int node, int left, int right, int ql, int qr) {
        if (qr < left || right < ql) return;
        if (ql <= left && right <= qr) {
            apply(node, left, right);
            return;
        }
        push(node, left, right);
        int mid = left + (right - left) / 2;
        toggle(node * 2, left, mid, ql, qr);
        toggle(node * 2 + 1, mid + 1, right, ql, qr);
        on[node] = on[node * 2] + on[node * 2 + 1];
    }

    int countOn(int node, int left, int right, int ql, int qr) {
        if (qr < left || right < ql) return 0;
        if (ql <= left && right <= qr) return on[node];
        push(node, left, right);
        int mid = left + (right - left) / 2;
        return countOn(node * 2, left, mid, ql, qr)
             + countOn(node * 2 + 1, mid + 1, right, ql, qr);
    }

public:
    explicit SegmentTree(int size) : n(size), on(4 * size, 0), lazy(4 * size, false) {}

    void toggle(int left, int right) {
        toggle(1, 1, n, left, right);
    }

    int countOn(int left, int right) {
        return countOn(1, 1, n, left, right);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    SegmentTree tree(n);

    while (m--) {
        int operation, left, right;
        cin >> operation >> left >> right;
        if (operation == 0) {
            tree.toggle(left, right);
        } else {
            cout << tree.countOn(left, right) << '\n';
        }
    }
    return 0;
}