개요

백준16713: Generic Queries

• 입력
  첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$)

  둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$)

  그 후, $Q$개의 줄에 걸쳐서, 각 줄마다 하나의 쿼리 $s_i, e_i$가 공백을 사이에 두고 주어진다. ($1 \le s_i \le e_i \le N$)

• 출력
  모든 쿼리의 답을 XOR한 값을 출력하시오.

접근 방식

1. xor연산에 익숙하지 않다보니, 0과 1을 가지고 xor연산을 했을 때
   같으면 0, 다르면 1이 나온다는 거만 알아서 접근을 어떻게 해야 할지 몰랐다.

2. 검색을 한 결과 구간합배열을 사용해 푸는 방식과 똑같이 풀면 되었었다.

3. 입력값을 받을 때 미리 누적 xor 배열을 만들어서 계산하면서 진행하였다.

	for (int i = 0; i < N; i++) {
		cin >> elem;
		//i+1은 i번째 값까지 xor연산한 누적xor배열
		xorPrefixSum[i + 1] = xorPrefixSum[i] ^ elem;
	}

4. 그 후 Q개의 쿼리 값을 진행하면서,
   그 구간 사이 값을 xor연산을 하고, xor연산값을 답 변수인 ans에 xor연산해준다

	for (int i = 0; i < Q; i++) {
			cin >> tmp >> tmp1;
			//답은 모든 쿼리문에 대해 xor연산한게 답이므로 
			//각 쿼리 끝부분인 tmp1, tmp-1을 xor연산해주고 답변수인 ans에 한번 더 xor연산 해준다.
			ans ^= xorPrefixSum[tmp1] ^ xorPrefixSum[tmp-1];
	}

코드

#include<iostream>

using namespace std;
int N=0, Q = 0,ans=0;
int xorPrefixSum[1'000'001];
void Input() {
	int elem = 0,tmp=0,tmp1=0;
	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		cin >> elem;
		//i+1은 i번째 값까지 xor연산한 누적xor배열
		xorPrefixSum[i + 1] = xorPrefixSum[i] ^ elem;
	}
		for (int i = 0; i < Q; i++) {
			cin >> tmp >> tmp1;
			//답은 모든 쿼리문에 대해 xor연산한게 답이므로 
			//각 쿼리 끝부분인 tmp1, tmp-1을 xor연산해주고 답변수인 ans에 한번 더 xor연산 해준다.
			ans ^= xorPrefixSum[tmp1] ^ xorPrefixSum[tmp-1];
		}
	cout << ans;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();

}

문풀후생

덧셈을 이용한 구간합배열이면 처음 값을 0으로 하면 더하면서 진행이 되었는 데, xor연산을 이용한 구간xor배열이면 처음값을 뭘해야 자신의 값이 나오는지 몰랐었다.

하지만 생각해보니 서로 다른 값이면 1이 나오고 같은 값이면 0이 나오는 특성상, 0인 값에 어떤걸 xor연산을 하든 자기 자신의 값이 나왔다.

마찬가지로 xor연산을 자기자신값에 넣으면 비트가 같으므로 0이 나온다.

xor연산에 대해 좀 배웠던 문제였다.