[BOJ/Silver 3] 백준 16713 Generic Queries(C++)

문제 링크

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

16713번: Generic Queries

 

문제

관영이는 쿼리를 좋아하고, XOR도 좋아한다. 그래서 관영이는 XOR을 이용한 쿼리 문제를 좋아한다.

길이가 N인 수열 a1,a2,⋯aN이 있다. 

이제 관영이는 Q개의 쿼리에 답하려 한다. 각 쿼리는 si,ei(1≤si≤ei≤N)의 형태로 들어오고, 그 쿼리의 답은 asi,asi+1,⋯aei을 모두 XOR한 값이다. 

 Q개의 쿼리가 들어올 때, 각 쿼리의 답을 모두 XOR한 결과를 구하시오. 

입력

첫째 줄에는 N,Q가 공백을 사이에 두고 주어진다. (1≤N≤10^6, 1≤Q≤3⋅10^6)

둘째 줄에는 a1,a2,⋯aN이 공백을 사이에 두고 주어진다. (0≤ai≤10^9)

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

출력

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

예제 입력 1

5 3
4 4 4 4 4
1 1
1 2
1 3

예제 출력 1

0

예제 입력 2

5 4
4 4 2 1 0
1 1
1 2
1 3
2 4

예제 출력 2

1

알고리즘 분류

• 누적 합

풀이

N개의 값을 입력받으면서 누적 XOR 연산값을 기록해준다.

그리고 구간 S, E를 입력받으면 구간 S에서 E까지의 XOR 연산값을 Answer변수와 XOR 연산해준다. 이것을 Q번 반복하여 나오는 Answer 변수에 담긴 값이 답이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1000001
#define LL long long
#define INF 1e12

using namespace std;
int N, Q;
LL Sum[MAX];
LL Answer = 0;

void Input() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		int T;
		cin >> T;
		Sum[i] = Sum[i - 1] ^ T;
	}
}

void Settings() {
	while (Q--) {
		int S, E;
		cin >> S >> E;
		Answer ^= (Sum[E] ^ Sum[S - 1]);
	};
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}