백준 1395번 스위치 (C++)

네이버 블로그에 한 번 정리했었던 Lazy Propagation을 활용한 세그먼트 트리 문제이다.

문제링크

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

설명

Lazy Propagation을 활용한 세그먼트 트리이다.
특정 구간의 스위치를 모두 변환시켜주는 대신 상위 노드의 개수만 변경해주고 하위 노드에는 표시만 해둔다.
이후 특정 구간의 켜진 스위치의 개수를 구할 때, 만약 해당 노드가 표시된 노드라면 스위치 개수를 변환해주고 표시를 해제한다.
이 때, 마찬가지로 하위 노드에 표시를 해둔다.

모든 스위치를 변환하지 않기 때문에 O(m * log n) 안에 문제를 해결할 수 있다.

처음에 스위치가 모두 꺼진 상태인데, 켜진 상태로 풀었다가 틀려서 멘붕왔었다. 앞으로는 문제를 더 꼼꼼히 읽자.

(초1 때부터 했던 다짐인 거 같기도...?)

코드

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> switchtree(262144);

void updateswitchtree(int start, int end, int node)
{
	if (switchtree[node].second)
	{
		switchtree[node].first = (end - start + 1) - switchtree[node].first;
		if (start != end)
		{
			switchtree[node * 2].second = !switchtree[node * 2].second;
			switchtree[node * 2 + 1].second = !switchtree[node * 2 + 1].second;
		}
		switchtree[node].second = 0;
	}
}

void changestatus(int start, int end, int left, int right, int node)
{
	updateswitchtree(start, end, node);

	if (start > right || end < left)
		return;

	if (start >= left && end <= right)
	{
		switchtree[node].second = !switchtree[node].second;
		updateswitchtree(start, end, node);
		return;
	}

	int mid = (start + end) / 2;

	changestatus(start, mid, left, right, node * 2);
	changestatus(mid + 1, end, left, right, node * 2 + 1);
	switchtree[node].first = switchtree[node * 2].first + switchtree[node * 2 + 1].first;
}

int getvalue(int start, int end, int left, int right, int node)
{
	updateswitchtree(start, end, node);

	if (start > right || end < left)
		return 0;

	if (start >= left && end <= right)
		return switchtree[node].first;

	int mid = (start + end) / 2;

	return getvalue(start, mid, left, right, node * 2) + getvalue(mid + 1, end, left, right, node * 2 + 1);
}

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

	int n, m, task, a, b;
	cin >> n >> m;
	while (m--)
	{
		cin >> task >> a >> b;
		if (task == 0)
			changestatus(0, n - 1, a - 1, b - 1, 1);
		else
			cout << getvalue(0, n - 1, a - 1, b - 1, 1) << '\n';
	}
	return 0;
}