JAVA 백준 16713 Generic Queries (누적합)

 

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

 

---

문제

1. 첫째 줄에 수열의 길이 N과 쿼리의 개수 Q ( 1 <= N <= 10 ^ 6 , 1 <= Q <= 3 *  10 ^ 6 ) 가 입력된다.
2. 둘째 줄에는 수열 a의 값들이 공백으로 구분되어 N개가 입력된다.
3. 셋째 줄부터 Q개의 줄에 쿼리 s, e ( 1 <= s, e <= N )가 공백으로 구분되어 입력된다.
4. 각 쿼리는 수열 a[ s ] ~ a[ e ] ( 1 <= a[ i ] <= 10 ^ 9 )의 값을 모두 XOR한 값이다.
5. 각 쿼리의 답을 모두 XOR한 결과를 출력하라.

---

 
 
 
초기 코드 (시간 초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        int[] a = new int[N];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        int[] answers = new int[Q];
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            int answer = 0;

            for (int j = s; j < e; j++) {
                if ((a[j] == 0 && a[j + 1] != 0) || (a[j] != 0 && a[j + 1] == 0)) {
                    answer = 1;
                } else {
                    answer = 0;
                }
            }

            answers[i] = answer;
        }

        int result = 0;

        for (int i = 0; i < Q-1; i++) {
            if ((answers[i] == 0 && answers[i + 1] != 0) || (answers[i] != 0 && answers[i + 1] == 0)) {
                result = 1;
            } else {
                result = 0;
            }
        }

        System.out.println(result);
    }
}

 
문제가 좀 불친절 한 것 같다.
어떻게 계산하는 건지 잘 모르겠어서 풀 방법을 잘 모르겠다.
 
XOR 연산이란 것은 수끼리 비트 XOR 연산을 하는 것이었다.
이 연산은 간단하게 ^ 연산으로 계산하면 수끼리의 XOR 계산을 해준다.
 
 
 
정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        int[] a = new int[N + 1];

        int[] xor = new int[N + 1];

        st = new StringTokenizer(br.readLine());

        for (int i = 1; i < N + 1; i++) {
            a[i] = Integer.parseInt(st.nextToken());

            xor[i] = xor[i - 1] ^ a[i];
        }

        int result = 0;

        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            result ^= xor[s - 1] ^ xor[e];
        }

        System.out.println(result);
    }
}

 
수열에 XOR 연산을 하여 누적합을 구해 배열에 저장하면 계산을 여러 번 하지 않아도 된다.
 
XOR 연산을 한 수에 다시 XOR 연산을 하면 원래의 수를 얻어낼 수 있다.
 
이 둘을 합쳐 각 쿼리의 값을 얻어내고 결과를 받을 변수에 얻어낸 수의 값을 XOR 하여 모든 쿼리를 반복하여 최종 답을 얻으면 된다.