[ BOJ ] 1395 : 스위치 ( PLATINUM 3 ) / C

문제

준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다.

준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다.

하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리하도록 결정하였다.

입력

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O가 0이면 Si번 스위치부터 Ti번 스위치까지 스위치 상태를 반전시키는 일이고 1이면 Si번 스위치부터 Ti번 스위치까지 중 켜져 있는 상태의 스위치 개수를 묻는 일이다. 단, 초기에는 모든 스위치의 상태는 꺼져있는 상태로 되어있다.

출력

입력에서 켜진 스위치 개수에 대한 답을 한 줄에 하나씩 출력한다.

풀이 과정

느리게 갱신되는 세그먼트 트리를 사용하여, 스위치를 (end-start+1) - tree[index] 식으로 반전시켰다.

#include <stdio.h>

int tree[400004] = {0,};
int lazy[400004] = {0,};

void update_lazy(int start, int end, int idx) {
	if (lazy[idx] != 0) {
		if (lazy[idx] % 2 == 1) {
			tree[idx] = (end - start + 1) - tree[idx];
			if (start != end) {
				lazy[idx * 2] += 1;
				lazy[idx * 2 + 1] += 1;
			}
		}
		
		lazy[idx] = 0;
	}
}

void update_range(int start, int end, int idx, int left, int right) {
	update_lazy(start, end, idx);
	if (end < left || right < start) return;
	if (left <= start && end <= right) {
		tree[idx] = (end - start + 1) - tree[idx];
		if (start != end) {
			lazy[idx * 2] += 1;
			lazy[idx * 2 + 1] += 1;
		}
		return;
	}

	int mid = (start + end) / 2;
	update_range(start, mid, idx * 2, left, right);
	update_range(mid + 1, end, idx * 2 + 1, left, right);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

int query(int start, int end, int idx, int left, int right) {
	update_lazy(start, end, idx);
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[idx];

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

// DEBUG
void printtree(int start, int end, int idx) {
	if (start == end) {
		printf("[%d] %d\n", start, tree[idx]);
		return;
	}
	else {
		printf("[%d-%d] %d\n", start, end, tree[idx]);
	}

	int mid = (start + end) / 2;
	printtree(start, mid, idx * 2);
	printtree(mid + 1, end, idx * 2 + 1);
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++) {
		//printtree(0, n - 1, 1);
		int mode, n1, n2;
		scanf("%d %d %d", &mode, &n1, &n2);
		if (mode == 0) update_range(0, n - 1, 1, n1 - 1, n2 - 1);
		else printf("%d\n", query(0, n - 1, 1, n1 - 1, n2 - 1));
	}
	return 0;
}