수열과 쿼리 5 [BOJ 13547]

서로 다른 수에 대한 쿼리를 다루는 문제 중 쉬운 문제로, 어려운 아이디어 없이도 해결할 수 있다. 이게 왜 P2일까...? 더 많은 풀이가 존재한다고 하는데, 필자의 풀이는 쉽다고 생각하여 P4를 기여했다. 풀고 난 뒤 다른 사람 코드를 보며 이 문제를 푸는 다른 방법에 대해 찾아보는 것도 재미있다.

 

문제 요약

길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다.

i j : 구간 [i, j]에 존재하는 서로 다른 수의 개수를 출력

 

사용 알고리즘

Mo's Algorithm

 

풀이

Mo's Algorithm을 사용하여 쿼리를 처리할 것이고, 새로운 배열 B[]와 변수 result를 관리할 것이다.

B[i]는 해당 구간에 들어있는 숫자 i의 개수, result는 해당 구간에 들어있는 서로 다른 숫자의 개수이다.

쿼리 간 이동하며 해당 구간에 숫자가 추가/제거될텐데, B[]는 새로 들어오는 숫자의 위치에 +1 또는 -1을 해주어 쉽게 고칠 수 있다. 또한 result는 B[]가 변하면서 0에서 1이 되었다면 +1, 1에서 0이 되었다면 -1을 해주면 된다.

 

코드

#include <bits/stdc++.h>
#define SIZE 1000010
using namespace std;
struct Query
{
    int idx,s,e;
};
Query Q[SIZE];
int N,M,A[SIZE],B[SIZE],ans[SIZE],res,sqrtN;
bool comp(Query x,Query y)
{
    if(x.s/sqrtN==y.s/sqrtN)return x.e<y.e;
    return x.s<y.s;
}
void mo_add(int x)
{
    if(B[A[x]]==0)res++;
    B[A[x]]++;
}
void mo_dis(int x)
{
    if(B[A[x]]==1)res--;
    B[A[x]]--;
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>N;
    sqrtN=sqrt(N);
    for(int i=1;i<=N;i++)cin>>A[i];
    cin>>M;
    for(int i=1;i<=M;i++){
        cin>>Q[i].s>>Q[i].e;
        Q[i].idx=i;
    }
    sort(Q+1,Q+M+1,comp);
    int s=Q[1].s,e=Q[1].e;
    for(int i=s;i<=e;i++)mo_add(i);
    ans[Q[1].idx]=res;
    for(int i=2;i<=M;i++){
        while(s<Q[i].s)mo_dis(s++);
        while(s>Q[i].s)mo_add(--s);
        while(e<Q[i].e)mo_add(++e);
        while(e>Q[i].e)mo_dis(e--);
        ans[Q[i].idx]=res;
    }
    for(int i=1;i<=M;i++)cout<<ans[i]<<'\n';
}

 

https://unorderedmap.tistory.com/13