c언어 1395번 스위치 (백준)

#include <stdio.h>

int tree[400000] = {}; //segment tree
char lazy[400000] = {}; //0이면 none, 1이면 스위치를 반전시켜야 한다는 의미

int lazyUpdate (int s, int e, int node) { //lazy propagation
	if(lazy[node]) { //1이라면 이 범위의 스위치들의 상태를 반전시켜야 함
		tree[node] = (e-s+1)-tree[node]; //범위의 개수에 기존의 스위치 중 켜져 있는 것을 빼면 반전된 스위치 중 켜져 있는 개수를 의미하게 됨
		if(s!=e) { //말단 노드가 아니라면
			lazy[node*2] ^= lazy[node]; //0이면 1이, 1이면 0이 됨
			lazy[node*2+1] ^= lazy[node];
		}
		lazy[node] = 0; //미루던 것을 처리했으니 0으로
	}
}
void update(int s, int e, int node, int l, int r) {
	lazyUpdate(s,e,node); //먼저 이전에 미뤄둔 것이 있는지
	if(s>r || e<l) return;
	if(l<=s && e<=r) { //범위에 속하면
		tree[node] = (e-s+1)-tree[node]; //개수를 반전
		if(s!=e) { //말단 노드가 아니라면, 자식노드에게 반전할 것을 미뤄둠
			lazy[node*2] ^= 1; //0이면 1이, 1이면 0이 됨
			lazy[node*2+1] ^= 1;
		} return;
	}
	int m=(s+e)/2;
	update(s,m,node*2,l,r);
	update(m+1,e,node*2+1,l,r);
	tree[node] = tree[node*2]+tree[node*2+1];
	return;
}

int find(int s, int e, int node, int l, int r) { //탐색
	lazyUpdate(s,e,node); //먼저 이전에 미뤄둔 것이 있는지
	if(s>r || e<l) return 0; //범위를 벗어났다면
	if(l<=s && e<=r) return tree[node]; //s~e가 l~r 범위에 들어 왔다면
	int m=(s+e)/2;
	return find(s,m,node*2,l,r)+find(m+1,e,node*2+1,l,r);
}

int main(void) {
	int n,m;
	scanf("%d %d",&n,&m);
	while(m--) {
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		if(a==0) update(1,n,1,b,c);
		else if(a==1) printf("%d\n",find(1,n,1,b,c));
	}
}

 

풀이 : 느리게 갱신되는 세그먼트 트리 (lazy propagation)

 

0. segment tree, lazy propagation 을 위한 배열을 0으로 초기화 해서 준비합니다.

 

1. lazyUpdate, update, find 함수를 준비합니다.

 

2. 스위치를 끄고 키는 것의 개수를 구하는 방법은

수정하는 범위의 개수 - 수정하는 범위에서 켜져있던 스위치의 개수  입니다.

 

3. lazy에 들어가는 값은 0, 1 뿐입니다. 이것은 xor 1 을 통해 쉽게 반전시킬 수 있습니다.

값이 0, 1뿐인 이유는 스위치에게 미뤄둔 일은 없다!, 있다!  두 가지 뿐이며, 특정 스위치를 반전 시키는 것이 2개가 쌓이면 (미뤄짐) 이것은 반전을 시키지 않은 것과 마찬가지이므로 0, 1 이 두가지만으로 처리할 수 있습니다. (on -> off -> on 이므로 굳이 반전을 두번 할 필요 없이, 그냥 안하면 됩니다)

 

4. 입력 받은 대로 쿼리를 처리하면 됩니다.

 0을 입력받으면 update, 1을 입력받으면 find

 

주의 : 이 문제에선 쿼리 이전에 기본값들이 주어지지 않기 때문에, 세그먼트 트리를 0으로 초기화 한 상태에서 바로 update, find을 진행했습니다. 만약 입력값이 따로 주어지는 문제라면, 입력값들을 가지고 segment tree을 초기화 해야 합니다.

 

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