[자료구조] 백준 1395번: 스위치 (C++)

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

1395번: 스위치

이번 문제는 구간 합 lazy propagation을 조금만 응용하면 풀릴 줄 알았다.

하지만, 이 문제는 세그먼트 트리와 lazy propagation을 정확히 꿰뚫고 있어야 풀리는 문제다.

 

맨 처음에 떠올린 방법은 leaf노드에 도달하면 leaf노드가 0이면 1, 1이면 0의 방식으로 전환을 해주고, 업데이트를 하면 될 거라고 생각했다. 이렇게 되면 따져야 할 조건이 많아질뿐더러 복잡해지고, 안 그래도 더러운 코드(세그먼트 트리 특징)를 더 더럽힐 생각을 하니 엄두가 안 났다.

 

구간 합과 비교하면서 하나씩 차근차근 뜯어보기로 했다.

정말 정말 간단하게 생각해야 된다.

몇 시간 동안 보면서 든 생각인데 한 줄의 코드를 고치는 것을 너무 겁내면 안 된다.

(물론 그만큼 그 알고리즘에 대해 빠삭하다면 고치는 게 두렵진 않았겠지...)

 

일단 세그먼트 트리를 구성하는 함수(init)는 이번 문제에 필요가 없었다.

다 꺼짐 상태로 시작한다고 했으니까 배열의 값도 0일 거고, 그로 인해 트리 값들도 다 0이기 때문이다.

 

우선 update함수를 콜 하면 lazyUpdate가 콜 되기 때문에 lazyUpdate부터 보도록 하자.

[구간 합 lazyUpdate -> 스위치 lazyUpdate]

void lazyUpdate(int node, int start, int end) {
	if (lazy[node] != 0) { // 해당 노드를 사용해야 하는데
		// 업데이트 해야 할 lazy 값이 있다면?
		sgTree[node] = sgTree[node] + (end - start + 1) * lazy[node];
		if (start != end) { // 자식 노드가 있다면?
			// 자식 노드에게 lazy 값 물려주기
			lazy[node * 2] = lazy[node * 2] + lazy[node];
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + lazy[node];
		}
		// 업데이트가 끝났으니 해당 노드의 lazy값 0
		// 이 부분은 자식 노드와 상관없으니 헷갈리지 말기
		lazy[node] = 0;
	}
}

우선 if문부터 고칠 수 있었다.

if (lazy[node] != 0) {
	// 코드 생략
}

기존의 구간합에서는 저 조건의 이유가 '업데이트할 값이 있다면 (코드 생략)해라'이었다.

즉, '업데이트할 무언가가 미뤄져 있다면 lazy 배열의 값들 업데이트시켜라'라는 뜻이 된다.

하지만, 스위치에서는 업데이트할 조건을 어떻게 따질까?

간단하다.

켜져 있는 스위치를 두 번 건드리면 켜져 있는 스위치가 되고, 한 번 건드리면 꺼져있는 스위치가 된다.

세 번 건드리면 꺼져있는 스위치가 된다.

즉, 업데이트해야 할 횟수(lazy값, 스위치를 건드는 횟수)가 홀수라면 업데이트를 해주어야 하고, 짝수라면 업데이트를 하나마나 똑같기 때문에 넘어간다.

if (lazy[node] % 2 == 1) {
	// 코드 생략
}

 

그다음 세그먼트 트리 노드에 갱신되는 값

sgTree[node] = sgTree[node] + (end - start + 1) * lazy[node];

구간 합에서는 업데이트할 값을 구간만큼 곱해서 기존 노드 값에 더해주었다.

하지만, 문제에서는 노드 값은 '현재 구간에서 스위치가 얼마나 켜져 있나?'를 묻기 때문에 현재 전체 구간 스위치의 개수에서 현재 켜져 있는 스위치의 개수만큼 빼주어야 한다.

그래야 켜져 있는 건 꺼지고, 꺼져있는 건 켜지기 때문이다.

sgTree[node] = (end - start + 1) - sgTree[node];

 

나머지 부분은 Lazy Propagation의 특성대로 자식 노드가 있다면 업데이트해야 할 횟수를 더해주고, 현재 노드는 업데이트를 했으니 0으로 바꿔주는 부분은 똑같았다.

[lazyUpdate (완성)]

void lazyUpdate(int start, int end, int node) {
	if (lazy[node] % 2 == 1) {
		sgTree[node] = (end - start + 1) - sgTree[node];
		if (start != end) {
			lazy[node * 2] = lazy[node * 2] + lazy[node];
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + lazy[node];
		}
		lazy[node] = 0;
	}
}

 

[구간 합 update -> 스위치 update]

void update(int node, int start, int end, int left, int right, ll value) {
	lazyUpdate(node, start, end);
	if (right < start || left > end) return;
	if (left <= start && end <= right) {
		sgTree[node] = sgTree[node] + (end - start + 1) * value;
		if (start != end) {
			lazy[node * 2] = lazy[node * 2] + value;
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + value;
		}
		return;
	}
	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, value);
	update(node * 2 + 1, mid + 1, end, left, right, value);
	sgTree[node] = sgTree[node * 2] + sgTree[node * 2 + 1];
}

우선 보이는 상황에서 바꿀 수 있는 부분은

1) value 인자가 필요 없다.

2) 세그먼트 트리 노드 갱신 방법

3) lazy 트리 갱신 방법

우선 1번, 2번만 바꿔주겠다.

void update(int node, int start, int end, int left, int right) {
	lazyUpdate(node, start, end);
	if (right < start || left > end) return;
	if (left <= start && end <= right) {
		sgTree[node] = (end - start + 1) - sgTree[node];
		if (start != end) {
			lazy[node * 2] = lazy[node * 2] + value;
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + value;
		}
		return;
	}
	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, value);
	update(node * 2 + 1, mid + 1, end, left, right, value);
	sgTree[node] = sgTree[node * 2] + sgTree[node * 2 + 1];
}

3번을 제외한 이유는 헷갈릴 여지가 있어서 설명하고 고치고 싶었다.

말 그대로 이번 세그먼트 트리에서 lazy 값은 업데이트할 횟수다.

value는 애초에 들어올 것이 없고, update 콜이 들어오면 자식(lazy 노드)들에게도 1을 더하여 update 콜이 들어왔었다고 알려주어야 하기 때문에 value가 아닌 1을 더해줘야 한다.

 

[구간합 query -> 스위치 query]

쿼리 부분은 사실상 몇 개 켜져 있는지 다 더해야 하는 것과 같아서 구간 합 쿼리와 똑같다.

[AC 코드]

#include <iostream>
#define MAX (100000 + 1)
using namespace std;

int arr[MAX];
int sgTree[MAX * 4];
int lazy[MAX * 4];
int n, m;

void lazyUpdate(int start, int end, int node) {
	if (lazy[node] % 2 == 1) {
		sgTree[node] = (end - start + 1) - sgTree[node];
		// 꺼진 스위치 개수 = 전체 구간의 스위치 수 - 현재 켜진 스위치 수
		if (start != end) {
			lazy[node * 2] = lazy[node * 2] + lazy[node];
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(int start, int end, int node, int left, int right) {
	lazyUpdate(start, end, node);
	if (right < start || left > end) return;
	if (left <= start && end <= right) {
		sgTree[node] = (end - start + 1) - sgTree[node];
		if (start != end) {
			lazy[node * 2] = lazy[node * 2] + 1;
			lazy[node * 2 + 1] = lazy[node * 2 + 1] + 1;
		}
		return;
	}

	int mid = (start + end) / 2;
	update(start, mid, node * 2, left, right);
	update(mid + 1, end, node * 2 + 1, left, right);
	sgTree[node] = sgTree[node * 2] + sgTree[node * 2 + 1];
}

int query(int start, int end, int node, int left, int right) {
	lazyUpdate(start, end, node);
	if (right < start || left > end) return 0;
	if (left <= start && end <= right) return sgTree[node];

	int mid = (start + end) / 2;
	return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, right);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int o, s, t;
		cin >> o >> s >> t;
		if (o == 0) {
			update(1, n, 1, s, t);
		}
		else {
			cout << query(1, n, 1, s, t) << '\n';
		}
	}
	return 0;
}

---

느낀 점

세그먼트 트리와 Lazy Propagation의 개념 공부를 더 확실시하고, 위에서 말했듯이 한 줄 한 줄 왜 그런지 따져보고, 한 줄 한 줄 고치는 것을 두려워하지 않아야 한다.