수열과 쿼리 38 [BOJ 18917]

실버도 문제다!

 

문제 요약

처음에 0이 하나 포함되어있는 배열 A에서 다음 4가지 쿼리를 수행한다.

1 x : 수열 맨 뒤에 x 추가

2 x : 수열에서 가장 앞에 있는 x 하나 제거

3 : 수열 원소 합 출력

4 : 수열 원소 XOR 출력

 

사용 알고리즘

없음

 

풀이

XOR의 성질에 따라 a^b^c^...^z에서 a^b^c^...^y를 구하고 싶으면 (a^b^c^...^z)^z를 하면 된다. XOR은 교환법칙과 결합법칙이 모두 성립하기 때문이다. 따라서 1, 2번 연산을 하면서 수열 원소 합/수열 원소 XOR을 관리해줄 수 있고, 출력만 하면 된다. 1번 쿼리에서 '맨 뒤에 추가', 2번 쿼리에서 '가장 앞에 있는 것 하나 제거'와 같은 내용은 문제를 거창하게 만들기 위한 도구이니 가볍게 무시해주자.

 

코드

#include <stdio.h>
int main()
{
    long long c=0, d=0;
    int query, q, x;
    scanf ("%d", &query);
    while (query--) {
        scanf ("%d", &q);
        if (q==1) {
            scanf ("%d", &x);
            c+=x, d^=x;
        }
        if (q==2) {
            scanf ("%d", &x);
            c-=x, d^=x;
        }
        if (q==3) printf("%lld\n", c);
        if (q==4) printf("%lld\n", d);
    }
}

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장