[백준 1395번] 스위치

---

1395번: 스위치

---

 

목차

• 사전 지식
• 문제 풀이

 

 

사전 지식

• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 알고 있어야 한다. (링크)

 

 

 

문제 풀이

구간 단위로 업데이트가 일어나므로 느리게 갱신되는 세그먼트 트리를 이용하면 된다.

 

구간 단위로 업데이트할 때 대응하는 노드에는 어떤 변화가 일어나는가

어떤 노드는 해당 구간에 켜져 있는 원소들의 개수를 저장하고 있다.
구간에 있는 원소들을 반전시키면 켜져 있는 원소들의 개수는 다음과 같이 변한다.
바뀐 값 = 구간의 크기 - 원래 값

 

propagate()를 할 때 어떤 일이 발생하는가

propagate()는 현재 노드의 정보를 자식 노드에게 전달하는 과정이다.
어떤 구간 연산을 홀수번하면 그대로이고, 짝수번하면 바뀐다.
즉, 넘겨줘야 하는 값은 그 구간의 변화가 홀수번인지, 짝수번인지에 대한 정보만 전달해 주면 된다.

 

	// BOJ 1395
	// Lazy SegTree
	#include <bits/stdc++.h>
	using namespace std;
	int sz;
	struct Seg {
	vector<int> tree, lazy;
	void build(int n) {
	for (sz=1; sz<n; sz*=2);
	tree.assign(2*sz, 0);
	lazy.assign(2*sz, 0);
	}
	void update(int l, int r, int n=1, int nl=0, int nr=sz-1) {
	propagate(n, nl, nr);
	if (nr<l || r<nl) return;
	if (l<=nl && nr<=r) {
	lazy[n] = 1;
	propagate(n, nl, nr);
	return;
	}
	int mid = (nl + nr) / 2;
	update(l, r, 2*n, nl, mid);
	update(l, r, 2*n+1, mid+1, nr);
	tree[n] = tree[2*n] + tree[2*n+1]; // update current(high-position) node
	}
	int query(int l, int r, int n=1, int nl=0, int nr=sz-1) {
	propagate(n, nl, nr);
	if (nr<l || r<nl) return 0;
	if (l<=nl && nr<=r) return tree[n];
	int mid = (nl + nr) / 2;
	return query(l, r, 2*n, nl, mid) + query(l, r, 2*n+1, mid+1, nr);
	}
	void propagate(int n, int nl, int nr) {
	if (lazy[n] != 0) {
	if (n < sz) { // (if not leaf node) propagate child node
	lazy[2*n] ^= lazy[n];
	lazy[2*n+1] ^= lazy[n];
	}
	// update current node
	if (lazy[n]) tree[n] = (nr-nl+1) - tree[n];
	lazy[n] = 0;
	}
	}
	} seg;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M; cin >> N >> M;
	seg.build(N);
	while (M--) {
	int op, a, b; cin >> op >> a >> b;
	if (op == 0) seg.update(a, b);
	if (op == 1) cout << seg.query(a, b) << '\n';
	}
	return 0;
	}

view raw 1395.cpp hosted with ❤ by GitHub