수열과 쿼리 20 [BOJ 16903]

수열에서 XOR 쿼리를 처리할 때 많이 사용하는 테크닉으로, 알아두면 좋다. 이 방법에 대해 조금 더 연습하고 싶다면 https://www.acmicpc.net/problem/20919 문제도 추천한다. 수열과 쿼리 20이 P2, 소개한 20919 문제가 P3로 되어있는데, 개인적으로 이 문제가 20919의 하위호환이라고 느껴 이 문제에는 P4를 기여했다. 그만큼 어려운 문제가 아니니 상위 플래 티어를 보고 쫄지 말고 스스로 고민하여 풀어보자.

 

문제 요약

0이 하나 포함되어 있는 배열 A에 다음 쿼리들을 20만 번 이하로 수행한다.

1 x : A에 x를 추가

2 x : A에 x를 제거(여러 개 있으면 하나만 제거)

3 x : A의 원소 A[i]들 중에서 A[i]^x의 최댓값을 출력

 

사용 알고리즘

트라이를 이용한 XOR 쿼리

 

풀이

왼쪽으로 내려갔을 때 0, 오른쪽으로 내려갔을 때 1인 이진 트리를 만든다고 생각하자.

예를 들어 깊이가 3인 트리에서 왼쪽-오른쪽-오른쪽으로 내려갔다면 이진수로 011, 즉 3을 의미하는 것이다.

이렇게 모든 수를 표현할 수 있다면, O(logX)에 해당 수에 대한 쿼리들을 다룰 수 있을 것으로 보인다(X는 입력으로 주어지는 수의 범위).

다만 이 문제에서 입력으로 주어지는 x의 범위가 10^9까지이므로, 메모리를 미리 설정해놓으면 당연히 메모리 초과가 난다. 따라서 트라이를 이용하여 1번 쿼리를 수행하는 중 새로운 메모리가 필요할 때마다 메모리를 할당해주는 방식을 사용한다. 각 노드에는 자신의 왼쪽 노드의 인덱스와 오른쪽 노드의 인덱스를 저장해줌으로써 관리할 수 있다. 1번 쿼리는 Q번 수행되며, 각 숫자가 독립적으로 메모리를 사용한다고 하더라도 각 숫자마다 logX개를 사용하므로 공간복잡도 O(QlogX)에 저장할 수 있다. 상수가 매우 작아서 실제로는 메모리가 훨씬 덜 든다.

2번 쿼리를 처리할 때 주의해야하는 점은 제거하는 숫자가 여러 개 있는지 판단하는 것인데, 이는 각 노드에 '현재 수열에 존재하는 수들 중 이 노드를 지나가는 숫자의 개수'를 저장해주면 간단하게 해결할 수 있다. 제거하여 숫자가 없어지더라도 메모리를 삭제하는 것이 아니라 해당 노드를 지나가는 숫자의 수가 0이라는 것을 통해 더 이상 숫자가 없다는 것을 알릴 수 있다.

3번 쿼리를 처리할 때에는 그리디하게 선택한다. 현재 노드에서 한 방향 길만 존재하는 경우 그리로 가면 되고, 0과 1 모두 존재하면 항상 주어진 수와 다른 비트를 택하면 된다. 해당 노드보다 더 깊은 노드들에서 최적으로 선택한다고 하더라도 현재 노드의 값보다 커지지 않기 때문이다. 0으로 가는 길과 1로 가는 길이 모두 없는 경우는 1번 쿼리와 2번 쿼리를 잘 처리해줬다면 생길 일이 없기 때문에 걱정하지 않아도 된다.

이렇게 3개의 쿼리를 모두 처리해줄 수 있고, 구현은 재귀함수로 하는 것이 가장 간편하다. 또한 각 노드는 왼쪽 인덱스, 오른쪽 인덱스, 그 노드를 지나오는 수의 개수를 저장해주는 구조체로 구성하였다. 트라이는 포인터로 구현하는 경우도 많은데, 개인적으로 인덱스를 이용한 구현이 더 직관적이고 활용도도 높다고 생각하여 이를 선호하는 편이다. 각 쿼리마다 트리를 따라 한 번 쭉 내려가는 것이 끝이므로 전체 O(QlogX)의 시간복잡도에 코드가 돌아가 문제를 해결할 수 있다.

 

코드

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int l,r,cnt;
};
vector<Node>v(1);
int M,tc,s;
void add(int x,int z,int idx)
{
    if(idx>=v.size())v.resize(idx+1);
    v[idx].cnt++;
    if(z==-1)return;
    if(x<(1<<z)){
        if(!v[idx].l)v[idx].l=v.size();
        add(x,z-1,v[idx].l);
    }
    else{
        if(!v[idx].r)v[idx].r=v.size();
        add(x-(1<<z),z-1,v[idx].r);
    }
}
void rem(int x,int z,int idx)
{
    v[idx].cnt--;
    if(z==-1)return;
    if(x<(1<<z))rem(x,z-1,v[idx].l);
    else rem(x-(1<<z),z-1,v[idx].r);
}
int que(int x,int z,int idx)
{
    if(z==-1)return 0;
    if(x<(1<<z)){
        if(v[idx].r>0&&v[v[idx].r].cnt>0)return (1<<z)+que(x,z-1,v[idx].r);
        return que(x,z-1,v[idx].l);
    }
    else{
        if(v[idx].l>0&&v[v[idx].l].cnt>0)return (1<<z)+que(x-(1<<z),z-1,v[idx].l);
        return que(x-(1<<z),z-1,v[idx].r);
    }
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    add(0,30,0);
    for(cin>>M;M--;){
        cin>>tc>>s;
        if(tc==1)add(s,30,0);
        if(tc==2)rem(s,30,0);
        if(tc==3)cout<<que(s,30,0)<<'\n';
    }
}