수열과 쿼리 11 [BOJ 13704]

재밌는데 고려할게 많아서 조금 귀찮다. 처음 풀 때는 12번만에 맞았고, 다시 풀 때도 한 번 틀렸다. 디테일한 구현을 많이 해보지 않았다면 한 번에 AC를 받기에는 어려울 수도 있는 문제이기에 비슷한 난이도의 아이디어를 가진 문제들보다 더 높은 티어를 받은 것 같다.

 

문제 요약

길이 10만 이하의 수열 A와 100만 이하의 수 K에 대하여 다음 쿼리를 수행한다.

l r : 구간 [l, r]에 포함되는 구간 [i, j] 중 A[i]^A[i+1]^...^A[j]=K인 구간의 수를 출력

 

사용 알고리즘

Mo's Algorithm

 

풀이

XOR의 성질에 따라 어떤 구간의 XOR 값은 누적 XOR을 통해 O(N)에 전처리하여 O(1)에 구할 수 있다. B[i]를 A[1]^...^A[i]라고 하면, A[i]^...^A[j]=B[i-1]^B[j]로 계산할 수 있다. 여기서는 B[i-1]^B[j]=K인 경우를 구하고 싶어하므로, 어떤 수 B[x]가 추가된다면 현재 구간에 있는 B[i]들 중 B[x]^K가 몇 개 있는지 세주면 될 것이다.

여기서 Mo's Algorithm의 아이디어를 떠올리는 것은 어렵지 않다. 오프라인 쿼리이기도 하고, 구간을 늘리고 줄일 때 O(1)에 갱신할 수 있기 때문이다. 새로운 배열 C를 하나 만들어 C[i]에는 현재 구간에 있는 수 들 중 B[x]=i인 x가 몇 개인지 저장해주면 된다. 이를 통해 Mo's Algorithm에 따라 쿼리를 정렬해준 후 쿼리 간 이동하며 답을 갱신해주면 된다. 이렇게 전체 시간복잡도 O(NsqrtN)에 문제를 해결할 수 있다.

주의할 점은 크게 세 가지 정도가 있다.

첫째, C 배열의 크기이다. C는 B의 원소를 인덱스로 가지기 때문에, B의 원소가 가질 수 있는 수의 범위를 알아야한다. A[i]의 범위가 100만이라고 해서 똑같이 100만이라고 착각해서는 안되고, 1<<20 미만의 모든 수를 가질 수 있기에 범위를 최소 1<<20만큼 잡아주어야한다. 사실 그냥 대충 크게 잡아도 상관은 없다.

둘째, 실제 쿼리나 구간에서 [i, j]를 다루기 위해서는 누적XOR 배열의 구간 [i-1, j]를 다루어야한다. 이를 신경쓰는 다양한 방법이 있는데, 가장 편한 방법은 쿼리 자체를 [l, r]에서 [l-1, r]로 만드는 것이다.

셋째, 하나의 쿼리에서 다른 쿼리로 이동하면서 현재 구간에 수를 추가/제거할 때 배열 C를 갱신하는 것과 답을 갱신하는 것의 순서를 잘 결정해주어야 한다. 3개의 주의할 점들 중에서 가장 중요하며, 틀리기 쉽다. 두 일의 순서가 결정하는 것은 B[x]^K=B[i]인 i들의 개수를 셀 때 i=x인 경우도 고려하는지이다. 즉, K=0인 경우 문제가 된다. 생각해보면 B[x]^B[x]는 구간 [x+1, x]를 고려하는 것으로, 실제 수열에는 없는 구간이다. 따라서 i=x인 경우를 고려하지 않도록 짜면 되고, 추가 또는 제거할 때 어떤 일을 먼저 수행해야 i=x인 경우를 고려하지 않게 되는지는 스스로 먼저 생각해보고 아래 코드를 참고하기 바란다. 이 부분을 맞게 구현했는지는 K=0이고 A[i]가 모두 0인 tc를 넣어보면 확인할 수 있다.

 

코드

**실제 구현에서는 누적XOR 배열을 따로 만들지 않고 그냥 A에 값들을 저장했다. 또한 아래 코드에서 배열 B는 위 풀이에서 배열 C를 의미한다.

#include<bits/stdc++.h>
#define SIZE 1<<20
using namespace std;
typedef long long ll;
struct query
{
    int s,e,idx;
};
int N,M,K,sqrtN,A[SIZE],B[SIZE];
ll res,ans[SIZE];
query q[SIZE];
bool comp(query x,query y)
{
    if(x.s/sqrtN==y.s/sqrtN)return x.e<y.e;
    return x.s<y.s;
}
void add(int i)
{
    res+=B[K^A[i]];
    B[A[i]]++;
}
void rem(int i)
{
    B[A[i]]--;
    res-=B[K^A[i]];
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>N>>K;
    sqrtN=sqrt(N);
    for(int i=1;i<=N;i++){
        cin>>A[i];
        A[i]^=A[i-1];
    }
    cin>>M;
    for(int i=1;i<=M;i++){
        cin>>q[i].s>>q[i].e;
        q[i].idx=i,q[i].s--;
    }
    sort(q+1,q+M+1,comp);
    int l=q[1].s,r=q[1].e;
    for(int i=l;i<=r;i++)add(i);
    ans[q[1].idx]=res;
    for(int i=2;i<=M;i++){
        while(l>q[i].s)add(--l);
        while(l<q[i].s)rem(l++);
        while(r>q[i].e)rem(r--);
        while(r<q[i].e)add(++r);
        ans[q[i].idx]=res;
    }
    for(int i=1;i<=M;i++)cout<<ans[i]<<'\n';
}

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장