c언어 12844번 XOR (백준)

#include <stdio.h>
int arr[500000] = {};
int tree[2000000] = {};
int lazy[2000000] = {};

int init(int s, int e, int node) {
	if(s==e) return tree[node] = arr[s];
	int m=(s+e)/2;
	return tree[node] = init(s,m,node*2)^init(m+1,e,node*2+1);
}

void lazyUpdate(int s, int e, int node) {
	if(lazy[node]) {
		if(((e-s)&1)==0) tree[node] ^= lazy[node];
		
		if(s!=e) {
			lazy[node*2] ^= lazy[node];
			lazy[node*2+1] ^= lazy[node];
		} lazy[node] = 0;
	}
}

void update(int s, int e, int node, int l, int r, int dif) {
	lazyUpdate(s,e,node);
	if(l>e || r<s) return;
	if(l<=s && e<=r) {
		if(((e-s)&1)==0) tree[node] ^= dif;
		
		if(s!=e) {
			lazy[node*2] ^= dif;
			lazy[node*2+1] ^= dif;
		}
		return;
	}
	int m=(s+e)/2;
	update(s,m,node*2,l,r,dif);
	update(m+1,e,node*2+1,l,r,dif);
	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(l>e || r<s) return 0;
	if(l<=s && e<=r) return tree[node];
	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",&n);
	for(int i=0; i<n; i++) scanf("%d",&arr[i]);
	init(0,n-1,1);
	scanf("%d",&m);
	while(m--) {
		int a,b,c,d;
		scanf("%d %d %d",&a,&b,&c);
		if(a==1) {
			scanf("%d", &d);
			update(0,n-1,1,b,c,d);
		}
		else if(a==2) {
			printf("%d\n",find(0,n-1,1,b,c));
		}
	}
}

 

풀이 : lazy propagation, xor

 

구간 수정을 하기 때문에 lazy propagation을 사용합니다.

 

구간 내 모든 수에 xor을 해야하나 xor의 특성상

(1. X xor 0 = X           2. X xor X = 0)

값을 수정할 때 수정하는 범위가 홀수 인 경우에만 한 번 xor을 해주기만 하면 됩니다.

짝수인 경우 어차피 그대로 입니다.

 

0. 입력을 받을 배열 (arr), 세그먼트 트리 (tree), lazy propagation 을 위한 또다른 트리 (lazy) 을 준비합니다.

 

1. 입력값을 받고, arr로 tree를 init(초기화) 해줍니다. 말단노드의 값은 arr, 부모노드의 값은 자식노드 값들을 xor한 값이 됩니다.

 

2. lazyUpdate, update, find 함수를 준비합니다. 각각 lazy propagation, 수정, 탐색을 위한 용도입니다.

 

3. find을 할 때는 범위에 들어온 값들을 xor해서 가져옵니다.

 

4. update을 할 때는 수정하는 구간에 속하는 노드인 경우, xor을 하여 수정해줍니다. 단 범위가 홀수 크기이면 한 번 xor을 해주고, 짝수 크기라면 그냥 넘어갑니다 (할 필요가 없습니다)

 

5. lazyUpdate 는 find, update을 할 때 가장 먼저 실행되어야 합니다. 이전에 미뤄둔 수정이 있을 수 있기 때문입니다.

 

6. lazyUpdate에서도 범위가 (start ~ end) 홀수라면 xor을 한 번 해주고, 짝수이면 넘어갑니다.

 

7. lazyUpdate에서 말단 노드가 아닌 경우 자식노드에 나중에 xor해야 할 값을 넘겨주는데, 이 때도 +가 아니라 xor을 해야 합니다.(이유 : lazy[]에 들어가 있는 값은 언젠가 필요할 때, xor을 해줄 값입니다. lazy[]에 임의의 값이 들어있는 상태에서, 또 새롭게 xor 값이 들어오면, 이는 기존의 값을 xor 하고 그 다음 값을 xor하라는 의미이나, 이 것을 각각 저장 할 필요 없이, 그냥 두 개를 미리 xor하고 저장해 두면 됩니다)

 

8  if( (    (e-s)&1) ==0    ) tree[node] ^= dif;

이 부분이 범위의 크기가 홀수 인 경우 xor을 한 번 해주는 코드입니다.

(e-s)&1 == 0가 아니라 ((e-s)&1) ==0 인 이유는 ==의 우선순위가 &보다 높기 때문입니다.

 

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