BOJ 1395 스위치

www.acmicpc.net/problem/1395

1395번: 스위치

 

레이지 프로퍼게이션을 공부한지 한달 조금 안되었다.

 

구간합을 구하는 것에 더해서 구간 업데이트까지 가능하다고??

정말 대단한 알고리즘이다.

 

 

하여간 이걸 연습해야 하는데.. 레이지 프로퍼게이션에는 오일러 경로 테크닉이 자주 따라오는 거 같다.

이건 모르는거니 필요없는 것중에 연습을 좀 하고 있는데 굉장히 멋있는 문제인것 같아서 풀어봤다.

 

보통 레이지프로퍼게이션 입문은 구간합을 구하는 문제로 입문해서, 단순히 암기만 하면 그 외의 응용은 어렵다.

이 알고리즘을 얼마나 잘 사용하는가는 "프로퍼게이션을 어떤것을 할 것인가" 임에 틀림없다.

 

이 문제는 구간에서의 켜진 전구의 개수를 구한다.

따라서 꺼진 전구는 0, 켜진 전구는 1을 해놓고 구간합을 구하면 구간에서의 켜진 전구의 개수를 알 수 있다.

 

하지만 프로퍼게이션을 어떤 것을 할 것인가?? 가 문제이다.

단순히 더하기만 할 것인가??

 

처음다루는 알고리즘이다보니 여기서 시간을 많이 사용했다.

 

하지만 사냥꾼답게 해내고 말았다

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
vector<int> seg, lazy;
//lazy에는 스위치를 몇번 건드렸는지 저장
//seg에는 리프에는, 1이면 켜짐, 0이면 꺼짐을 저장.
//그러면 구간합 부분에는 자연스럽게 몇 개가 켜졌는지 저장.
void propogate(int i, int s, int e) {
	if (lazy[i] != 0) {
		if (i < k / 2) {
			//스위치 누른 횟수 내려주고
			lazy[i * 2] += lazy[i];
			lazy[i * 2 + 1] += lazy[i];
		}
		if (lazy[i] % 2) {
			//스위치를 홀수번 건드려야 스위치의 반전이 일어난다.
			seg[i] = (e - s + 1) - seg[i];
		}
		lazy[i] = 0;
	}
}

void update(int s, int e, int ns, int ne, int i, int plus) {
	propogate(i, ns, ne);
	if (ne < s || e < ns) return;
	if (s <= ns && ne <= e) {
		lazy[i] += plus;
		propogate(i, ns, ne);
		return;
	}
	update(s, e, ns, (ns + ne) / 2, i * 2, plus);
	update(s, e, (ns + ne) / 2 + 1, ne, i * 2 + 1, plus);
	seg[i] = seg[i * 2] + seg[i * 2 + 1];
}

int find(int s, int e, int ns, int ne, int i) {
	propogate(i, ns, ne);
	if (ne < s || e < ns) return 0;
	if (s <= ns && ne <= e) return seg[i];
	return find(s, e, ns, (ns + ne) / 2, i * 2) + find(s, e, (ns + ne) / 2 + 1, ne, i * 2 + 1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int m;
	cin >> n >> m;
	k = 1;
	while (k < n) k *= 2;
	k *= 2;
	seg.resize(k); lazy.resize(k);
	while (m--) {
		int flag;
		cin >> flag;
		if (flag) {
			int a, b; cin >> a >> b;
			cout << find(a, b, 1, k / 2, 1) << "\n";
		}
		else {
			int a, b; cin >> a >> b;
			update(a, b, 1, k / 2, 1, 1);
		}
	}
	return 0;
}

 

lazy에는 스위치를 몇번 눌렀는지를 넣어서 propogate해주면 된다.

현재 노드에서의 lazy값이 짝수라면 스위치를 짝수번 눌렀다는 것이고, 이는 구간의 켜진 스위치의 개수는 변함이 없다.

그러나 홀수라면? 해당 노드가 표현하는 범위의 스위치는 반전이 된다.

 

따라서 lazy를 상속을 해준 이후 현재 노드의 값은 lazy가 홀수일 때만 (구간의 노드의 개수 - 현재 켜진 스위치의 개수)로 바꾸어 주기만 하면 풀리는 문제이다.

 

레이지 프로퍼게이션을 이용하는 첫 응용문제로 도전하기 아주 좋은 난이도인 듯 하다.

이 기세를 이어 다른 문제들도 솔브 해보려 했으나.. 역시 어려운 알고리즘이다.