[백준 18917] 수열과 쿼리 38

수열과 쿼리 문제중에 아마 접근 아이디어가 가장 쉬운 문제가 아닐까 싶습니다.

 

문제 내용은 아주 단순합니다.

---

처음에 0이 하나 포함되어있는 배열 A가 있다. 이때, 다음 쿼리를 수행해야 한다.

• 1 x: A의 가장 뒤에 x를 추가한다.
• 2 x: A에서 x를 제거한다. A에 x가 두 개 이상 있는 경우에는 가장 앞에 있는 하나만 제거한다. 항상 A에 x가 있는 쿼리만 주어진다.
• 3: A에 포함된 모든 원소를 더한 값을 출력한다.
• 4: A에 포함된 모든 원소를 XOR한 값을 출력한다.

---

여기서 봐야할 건 "포함된 모든 원소" 라는 내용입니다.

 

평소 수열과 쿼리 문제에서 요구하는 건 어떠한 배열이 주어질 때 i ~ j 구간에서 요구하는 합계나 최댓값 등 세그먼트 트리를 이용해야 했습니다.

 

하지만 모든 원소를 구하라 했으니 문제가 매우 단순해집니다.

 

모든 원소를 더한 값 = 입력 될 때마다 누적 합

모든 원소를 XOR한 값 = 입력 될 때마다 XOR 수행

으로 표현됩니다. x의 갯수가 최대 50만, 범위가 0 ~ 10억까지니 long형으로 처리해야 합니다.

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int M = Integer.parseInt(br.readLine());
        long getSum = 0;
        long getXor = 0;
        while(M-->0) {
            int c = Integer.parseInt(br.readLine());
            if(c == 1) {
                long x = Long.parseLong(br.readLine());
                getSum += x;
                getXor ^= x;
            } else if(c == 2) {
                long x = Long.parseLong(br.readLine());
                getSum -= x;
                getXor ^= x;
            } else if(c == 3) {
                bw.write(Long.toString(getSum));
                bw.newLine();
            } else if(c == 4) {
                bw.write(Long.toString(getXor));
                bw.newLine();
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}