백준 1395 스위치 C++

Jan 11, 2024

이번에도 세그먼트 트리 문제다. 다만 그냥 세그먼트 트리를 사용할 경우, 구간 업데이트에 너무 많은 시간이 걸려 TLE 이므로 조금 다른 방식이 필요하다.

세그먼트 트리를 이용한 TLE코드

#include <bits/stdc++.h>
using namespace std;
int N, M;
int seg[100'000 << 2];

int update(int node, int s, int e, int a, int b)
{
	if (b < s || e < a) return seg[node];
	if (s == e) return seg[node] = 1 - seg[node];
	int mid = (s + e) / 2;
	return seg[node] = update(node * 2, s, mid, a, b) + update(node * 2 + 1, mid + 1, e, a, b);
}

int query(int node, int s, int e, int a, int b)
{
	if (b < s || e < a) return 0;
	if (a <= s && e <= b) return seg[node];
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, a, b) + query(node * 2 + 1, mid + 1, e, a, b);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> N >> M;
	int a, b, c;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b >> c;
		if (a == 0)
		{
			update(1, 1, N, b, c);
		}
		else
		{
			cout << query(1, 1, N, b, c) << '\n';
		}
	}
	return 0;
}

시간초과를 해결하기 위해서는 구간 업데이트에 사용되는 시간을 줄여야하는데 이때 사용되는 것이 lazy propagation(느린전파) 이다.

lazy propagation

느리게 갱신되는 세그먼트 트리라고도 불린다. 말 그대로 트리의 갱신이 느리게 진행된다. TLE 코드에서는 업데이트 시 리프노드부터 루트노드까지 갱신이 되는 반면, lazy propagation을 사용한다면, 갱신이 한번에 이루어지지 않는다.
구간 단위로 업데이트가 필요한 경우 주로 사용된다.

개념은 간단한데, 현재 노드가 갱신하려는 구간에 포함된다면, 해당 노드만 업데이트한 뒤 종료되며 자식노드의 갱신은 바로 이루어지지 않는다.
자식노드의 갱신은 나중에 노드의 정보가 필요해 그 노드에 방문할 때 처리하는데, 이를 위해 lazy배열에 갱신에 대한 정보를 저장해두어야한다.

만약 느리게 갱신되는 세그먼트 트리를 만들었다면, 앞으로의 모든 노드 방문에서는 해당노드에 대한 lazy값이 있는지의 여부를 확인해야한다.
이는 업데이트 뿐만 아니라, query를 수행할 때도 확인해줘야한다.

문제로 넘어가보자.
세그먼트트리와 느린전파에 대해 알고 문제를 보면 어려운 문제는 아니다.
핵심은 노드에 무엇을 저장할 지, lazy배열에 어떤 값을 넘길지만 생각해내면 된다.

노드에는 해당 구간에 켜져있는 전구의 개수를 저장하면 된다.
초기상태는 모두 꺼진 0이라 세그먼트 트리의 초기화는 필요가 없다.

해줘야하는 작업은 전구상태의 반전과 켜져있는 전구의 개수를 구하는 건데

켜져있는 전구의 개수는 노드에 켜진 전구의 개수를 저장하기에 해결되었고 반전시키는 작업만 해주면 된다.

(구간의 총 전구 개수) - (구간에 켜져있는 전구 개수)
=> end - start + 1 - seg[node]

lazy배열에 전달해야하는 값은 무엇일까?
반전을 시켰다면 값을 1 증가시키기만 하면 된다.
만약 두번 반전 시킨다면 1을 더 증가시켜 2인데, 이는 원래상태니까 lazy의 값이 짝수라면 유지, 홀수라면 반전시키면 된다.

#include <bits/stdc++.h>
using namespace std;
// lazy propagation
int N, M;
int seg[100'000 << 2];
int lazy[100'000 << 2];

void update(int node, int s, int e, int a, int b)
{
	if (lazy[node] != 0)//자식 전파
	{
		if (lazy[node] % 2 == 1) //홀수면
		{
			seg[node] = (e - s + 1) - seg[node];
		}
		if (s != e)
		{
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
	if (b < s || e < a) return;
	if (a <= s && e <= b)
	{
		seg[node] = (e - s + 1) - seg[node];
		if (s != e)
		{
			lazy[node * 2]++;
			lazy[node * 2 + 1]++;
		}
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, a, b);
	update(node * 2 + 1, mid + 1, e, a, b);
	seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

int query(int node, int s, int e, int a, int b)
{
	if (lazy[node] != 0)//자식 전파
	{
		if (lazy[node] % 2 == 1) //홀수면
		{
			seg[node] = (e - s + 1) - seg[node];
		}
		if (s != e)
		{
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
	if (b < s || e < a) return 0;
	if (a <= s && e <= b) return seg[node];
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, a, b) + query(node * 2 + 1, mid + 1, e, a, b);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> N >> M;
	int a, b, c;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b >> c;
		if (a == 0)
		{
			update(1, 1, N, b, c);
		}
		else
		{
			cout << query(1, 1, N, b, c) << '\n';
		}
	}
	return 0;
}