[백준 18917] 수열과 쿼리 38

작성일 | In |

문제 링크

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

풀이

배열에 들어온 $x$의 합과 XOR을 한 값을 각각 저장한 변수를 따로 둔다면 3번 쿼리와 4번 쿼리에 대한 답을 알 수 있습니다. 배열 $A$에 어떤 수가 추가된다면 그대로의 연산을 하고 두 연산 모두 역원(뺏셈, XOR)이 존재하기 때문에 어떤 수를 제거할 때는 역원으로 연산을 해주면 됩니다. 쿼리마다 $O(1)$연산만 하기 때문에 전체 시간복잡도는 $O(M)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, s, x;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    while(n--){
        int a, b; cin >> a;
        if(a == 1){
            cin >> b;
            s += b, x ^= b;
        }
        if(a == 2){
            cin >> b;
            s -= b, x ^= b;
        }
        if(a == 3){
            cout << s << '\n';
        }
        if(a == 4){
            cout << x << '\n';
        }
    }
}