BOJ 1395 스위치

사용한 알고리즘

세그먼트 트리, 레이지 프로퍼게이션

알고리즘 설명

세그먼트 트리는 하나의 값을 변경하기 위해서는 O(logN)만큼의 시간을 필요로 한다.
하지만 본 문제에서는 구간 값을 변경하는 형태이므로, 업데이트에 의한 시간초과가 발생할 수 있다.
이를 막기 위해서 세그먼트 트리의 구간에 대한 값을 변경할 때에 합을 요구하기 전까지 업데이트를 미루는 전략을 사용한다.
코드는 라이님 블로그 이해하고 작성하였다.
여기서 스위치는 ON/OFF 의 형태로 lazy 값은 bool 형태로 저장하였다.

풀이

#include <cstdio>
#include <algorithm>
using namespace std;
const int ST_SIZE=1<<18;

int N, M, seg[ST_SIZE];
bool lazy[ST_SIZE];

struct SegTree {
	int start, seg[ST_SIZE];
	bool lazy[ST_SIZE];

	SegTree() {
		start = ST_SIZE/2;
		fill(seg, seg+ST_SIZE, 0);
		fill(lazy, lazy+ST_SIZE, false);
	}

	// propagate in [ns, ne]
	void propagate(int node, int ns, int ne) {
		if (lazy[node]) {
			lazy[node] = false;
			if (node < start) {
				lazy[node*2] ^= 1;
				lazy[node*2+1] ^= 1;
				seg[node] = 0;
				if (lazy[node*2]) seg[node] += (ne-ns+1)/2 - seg[node*2];
				else seg[node] += seg[node*2];
				if (lazy[node*2+1]) seg[node] += (ne-ns+1)/2 - seg[node*2+1];
				else seg[node] += seg[node*2+1];
			}
			else seg[node] ^= 1;
		}
	}

	// reverse [ns, ne]
	void update(int s, int e) { update(s, e, 1, 0, start-1); }
	void update(int s, int e, int node, int ns, int ne) {
		propagate(node, ns, ne);

		if (e < ns || ne < s) return;
		if (s <= ns && ne <= e) {
			lazy[node] ^= 1;
			propagate(node, ns, ne);
			return;
		}
		int mid = (ns + ne)/2;
		update(s, e, node*2, ns, mid);
		update(s, e, node*2+1, mid+1, ne);
		seg[node] = seg[node*2] + seg[node*2+1];
	}

	// sum [ns, ne]
	int sum(int s, int e) { return sum(s, e, 1, 0, start-1); }
	int sum(int s, int e, int node, int ns, int ne) {
		propagate(node, ns, ne);
		if (e < ns || ne < s) return 0;
		if (s <= ns && ne <= e) return seg[node];
		int mid = (ns + ne)/2;
		return sum(s, e, node*2, ns, mid) + sum(s, e, node*2+1, mid+1, ne);
	}
};

int main() {
	scanf("%d%d", &N, &M);
	SegTree seg;
	for (int i=0; i<M; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (a == 0) seg.update(b, c);
		else printf("%d\n", seg.sum(b, c));
	}
	return 0;
}

참조

라이님 블로그