[알고리즘] 벡준 16713 누적 XOR문제

Generic Queries 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2.5 초

512 MB

1502

905

718

58.232%

문제

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

길이가 N$N$인 수열 a1,a2,⋯aN$a_1 , a_2 , \cdots a_N$이 있다. 

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

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

입력

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

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

그 후, Q$Q$개의 줄에 걸쳐서, 각 줄마다 하나의 쿼리 si,ei$s_i, e_i$가 공백을 사이에 두고 주어진다. (1≤si≤ei≤N$1 \le s_i \le e_i \le 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

 

정답 코드 

package test;

import java.util.*;
import java.io.*;

public class Solution{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static StringTokenizer st;
	static int N;
	static int Q;
	
	public static void main(String[] args) throws IOException{
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		int[] acc = new int[N+1];
		
		st = new StringTokenizer(br.readLine());
		
		//누적 XOR값을 인력을 받으면서 acc 배열에 입력
		for(int i =1; i <=N; i++) {
			acc[i] ^= Integer.parseInt(st.nextToken()) ^acc[i -1];
		}
		
		int ans =0;
		while(Q-- >0){
			
			// s와 e값을 인력 
			st = new StringTokenizer(br.readLine());
			
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			ans ^= acc[e] ^acc[s-1];
		}
		
		System.out.println(ans);
	
	}
}