c언어 16713번 Generic Queries (백준)

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int n, m, ans = 0;
	scanf("%d %d", &n, &m);
	
	int *a = (int*) malloc(4*(n+1)); //동적할당
	a[0] = 0;
	for(int i=1; i<=n; i++) { //요소들을 입력받고 이전에 xor 한 값에 xor 한다.
		scanf("%d",&a[i]);
		a[i] ^= a[i-1];
	}
	
	while(m--) { //쿼리들을 처리한다.
		int s, e;
		scanf("%d %d",&s,&e);
		ans ^= (a[e]^a[s-1]);
	} printf("%d", ans);
    free(a);
}

 

풀이 : 누적합, XOR

 

1. 요소의 개수와 쿼리의 개수를 입력

2. 누적합을 위해 동적할당

3. 쿼리 처리

 

XOR 의 특징

1. 연산순서는 상관이 없습니다

2. 어떠한 값에 x을 짝수번 xor한 값은 xor 하기 전과 같은 값입니다.(ex 0 xor 4 xor 4 = 0)

 

1, 2, 3, 4 을 xor 한다고 하면 순서는 상관 없습니다 결과는 같습니다.

 

즉 입력받은 요소들을 이전의 요소들의 xor한 결과에 xor을 한 것을 저장합니다. 누적합 처럼

 

만약 특정 범위의 xor을 한 값들을 알고 싶다면

ex) 3번째부터 5번째까지의 요소들의 xor 결과

1~5번째의 xor 결과에서 1~2번째의 xor 결과를 xor 해주면 됩니다.

 

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

16713번: Generic Queries