문제 링크: https://www.acmicpc.net/problem/18917

간단한 구현 문제입니다.

풀이

쿼리의 종류

4가지의 쿼리를 수행하면 됩니다.

1. 배열의 끝에 새 원소 $x$를 추가하기
2. 배열에서 원소 $x$를 제거하기

• 여러 개 있다면 제일 앞의 원소를 제거합니다.

3. 배열의 모든 원소의 합을 출력하기
4. 배열의 모든 원소를 XOR한 값을 출력하기

모든 원소의 합 계산하기

당연히 매 쿼리마다 배열 전체의 합을 구하는 것은 비효율적입니다. 대신에, 배열에 원소를 추가하고 제거할 때 마다 원소 합을 계산해두면 3번 쿼리를 $O(1)$에 수행할 수 있습니다.

모든 원소를 XOR한 값 계산하기

이 또한 원소의 합과 마찬가지로 배열에 수가 추가/제거될 때마다 미리 계산해두면 4번 쿼리를 $O(1)$시간에 구할 수 있습니다.

임의의 수 $a$에 대해, $a$에 $x$를 두 번 XOR하면 다시 $a$가 됩니다. 이를 이용해, 추가할 때 한 번, 제거할 때 한 번 XOR해주면 됩니다.

배열에 원소를 추가 / 제거하기

사실 실제로 배열에 원소를 추가하고 제거할 필요는 없습니다! 합과 XOR값을 미리 계산해둔다면, 배열에 원소를 저장하고 참조할 이유가 없기 때문입니다.

전체 코드

input = open(0).readline
xor = 0
sum = 0

for _ in range(int(input())):
    cmd = input().split()
    if cmd[0] == "3":
        print(sum)
    elif cmd[0] == "4":
        print(xor)
    elif cmd[0] == "1":
        x = int(cmd[1])
        sum += x
        xor ^= x
    elif cmd[0] == "2":
        x = int(cmd[1])
        sum -= x
        xor ^= x