[ 백준 1395 ] 스위치 (C++)

백준의 스위치(1395) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

스위치를 주어지는 구간에 몇 개가 켜져있는지 구해야 하는 문제이다.

또한, 스위치의 상태를 반전시키는 업데이트 연산 또한 구간으로 주어지게 된다.

그래서 본인은 구간에 대한 연산을 효율적으로 처리할 수 있는 세그먼트 트리로 접근해 보았다.

그런데 ! 업데이트 또한 구간으로 주어지기 때문에, Lazy Propagation을 이용해서 접근하였다.

아직 Lazy Propagation에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

(아래의 글을 들어가면, 세그먼트 트리에 대한 설명글로도 가실 수 있습니다.)

[ Lazy Propagation 알아보기(Click) ]

이제 이 문제에 맞게 세그먼트 트리를 구현해보자.

가장 초기에 스위치는 모두 꺼져있는 상태이므로, 어떤 구간에도 켜져있는 스위치는 존재하지 않는다. 따라서, 세그먼트 트리를 가장 초기에 만들어 줄 필요가 없다. 따라서 단순히 세그먼트 트리의 공간만 할당해주고 어떠한 데이터도 넣어주지 않았다.

그 이후에는 구간별로 커져있는 스위치의 갯수를 세그먼트 트리에 저장해주는 방식으로 진행하였다.

위의 링크가 걸려있는 글만 보더라도 충분히 풀이를 대체할 수 있을 거라 생각해서 더 이상의 설명은 하지 않겠다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, M;
int Switch[MAX];
vector<int> SegmentTree;
vector<int> Lazy;
vector<pair<int, pair<int, int>>> Cmd;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Cmd.push_back(make_pair(a, make_pair(b, c)));
    }
}
 
void Lazy_Update(int Node, int Start, int End)
{
    if (Lazy[Node] != 0)
    {
        SegmentTree[Node] = (End - Start + 1) - SegmentTree[Node];
        if (Start != End)
        {
            Lazy[Node * 2] = !Lazy[Node * 2];
            Lazy[Node * 2 + 1] = !Lazy[Node * 2 + 1];
        }
        Lazy[Node] = 0;
    }
}
 
void Update(int Node, int Start, int End, int Left, int Right)
{
    Lazy_Update(Node, Start, End);
    if (Right < Start || Left > End) return;
    if (Left <= Start && End <= Right)
    {
        SegmentTree[Node] = (End - Start + 1) - SegmentTree[Node];
        if (Start != End)
        {
            Lazy[Node * 2] = !Lazy[Node * 2];
            Lazy[Node * 2 + 1] = !Lazy[Node * 2 + 1];
        }
        return;
    }
 
    int Mid = (Start + End) / 2;
    Update(Node * 2, Start, Mid, Left, Right);
    Update(Node * 2 + 1, Mid + 1, End, Left, Right);
    SegmentTree[Node] = SegmentTree[Node * 2] + SegmentTree[Node * 2 + 1];
}
 
int Query(int Node, int Start, int End, int Left, int Right)
{
    Lazy_Update(Node, Start, End);
    if (Right < Start || Left > End) return 0;
    if (Left <= Start && End <= Right) return SegmentTree[Node];
 
    int Mid = (Start + End) / 2;
    int Left_Result = Query(Node * 2, Start, Mid, Left, Right);
    int Right_Result = Query(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Left_Result + Right_Result;
}
 
void Solution()
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = 1 << (Tree_Height + 1);
    SegmentTree.resize(Tree_Size, 0);
    Lazy.resize(Tree_Size);
    
    for (int i = 0; i < M; i++)
    {
        int Command = Cmd[i].first;
        if (Command == 0)
        {
            int Index = Cmd[i].second.first - 1;
            int Index2 = Cmd[i].second.second - 1;
            Update(1, 0, N - 1, Index, Index2);
            continue;
        }
 
        int Index = Cmd[i].second.first - 1;
        int Index2 = Cmd[i].second.second - 1;
        cout << Query(1, 0, N - 1, Index, Index2) << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}