BOJ 1395 스위치

문제

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

스위치 n개에 대하여 특정 구간의 스위치를 모두 반전시키거나, 구간에 있는 켜져 있는 스위치의 수를 세는 쿼리를 해결하는 문제이다.

 

풀이

세그먼트 트리를 이용한다.

세그먼트 트리의 각 노드가 해당 구간의 켜져 있는 스위치들의 수를 갖고 있다면, 2번째 쿼리는 쉽게 해결할 수 있다.

 

문제는 첫번째 쿼리가 하나의 스위치를 반전시키는 것이 아니라, 특정 구간의 모든 스위치들을 반전시키는 것이다.

따라서 세그먼트 트리 레이지 프로파게이션을 사용해야 한다.

 

레이지 배열에는 그 구간에 대한 반전 연산이 적용되었는가 여부를 저장한다.

구간합에 대한 레이지처럼 구간 업데이트를 할 때 자신이 완전히 속한 노드에 대해서, 레이지값을 자식들에게 넘겨주며, 뒤집어 주면 된다.

 

시간 복잡도 : $O(QlogN)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int n, m;

struct SEG
{
    int n; vector<int> tree, lazy;

    SEG(int n) : n(n), tree(n*4+10, 0), lazy(n*4+10, 0) {}

    void update_lazy(int node, int tl, int tr)
    {
        if(lazy[node]==0) return;
        tree[node]=(tr-tl+1)-tree[node];
        if(tl!=tr) { lazy[node*2]^=1; lazy[node*2+1]^=1; }
        lazy[node]=0;
    }

    void update(int node, int tl, int tr, int l, int r)
    {
        update_lazy(node, tl, tr);
        if(tr<l || r<tl) return;
        if(l<=tl && tr<=r)
        {
            tree[node]=(tr-tl+1)-tree[node];
            if(tl!=tr) { lazy[node*2]^=1; lazy[node*2+1]^=1; }
            return;
        }
        int mid=tl+tr>>1;
        update(node*2, tl, mid, l, r);
        update(node*2+1, mid+1, tr, l, r);
        tree[node]=tree[node*2]+tree[node*2+1];
    }

    int query(int node, int tl, int tr, int l, int r)
    {
        update_lazy(node, tl, tr);
        if(tr<l || r<tl) return 0;
        if(l<=tl && tr<=r) return tree[node];
        int mid=tl+tr>>1;
        return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
    }

    void update(int l, int r) { update(1, 1, n, l, r); }
    int query(int l, int r) { return query(1, 1, n, l, r); }
};

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d%d", &n, &m);
    SEG seg(n);
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(a==0) seg.update(b, c);
        else printf("%d\n", seg.query(b, c));
    }

    return 0;
}