BOJ 13547 - 수열과 쿼리 5

문제 링크 : https://www.acmicpc.net/problem/13547

문제 태그

Mo's algorithm

문제 소개

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다.

문제 풀이

수의 갯수를 출력하기 위해서는 수들의 집합을 관리 해야한다. 쿼리로써 구간을 많이 주는데 그 쿼리마다 수들의 집합을 관리해야한다 -> 바로 Mo's algorithm을 떠올릴 수 있다. 풀이도 꽤나 간단하게 보인다. 

Mo's algorithm을 이용하여 구간을 정렬하고 구간내에서의 각 숫자의 갯수를 세주면 된다. 구간을 추가할 때는 추가되는 구간의 숫자의 갯수에 1을 더해가고 구간을 뺄때는 빠지는 구간의 숫자의 갯수에 1을 빼면 된다.
이때 더하는 과정에서 없던 수를 처음으로 더하게 되면 답에 1을 더하고, 빼는 과정에서 뺌으로서 그 숫자가 구간내에서 사라지게 되면 답에 1을 빼면 된다. 따라서 각 구간 별로 바로 답을 구할 수 있다.

코드

 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct q{
    ll idx,s,e;
};
q qer[1010101];
ll ans[1010101];
ll cnt[1010101];
ll arr[1010101];
ll sqn;
ll now;
ll lf,rf;
 
bool sf(q a,q b)
{
    if(a.s/sqn!=b.s/sqn) return a.s<b.s;
    return a.e<b.e;
}
 
void mi(ll s, ll e)
{
    ll i;
    for(i=s;i<=e;i++)
    {
        cnt[arr[i]]--;
        if(cnt[arr[i]]==0) now--;
    }
}
 
void pl(ll s, ll e)
{
    ll i;
    for(i=s;i<=e;i++)
    {
        if(cnt[arr[i]]==0) now++;
        cnt[arr[i]]++;
    }
}
 
int main()
{
    ll i,j,k,l,m,n,Q;
    scanf("%lld",&n);
    sqn=sqrt(n);
    for(i=1;i<=n;i++)
        scanf("%lld",&arr[i]);
 
    scanf("%lld",&Q);
    for(i=1;i<=Q;i++)
    {
        scanf("%lld %lld",&qer[i].s,&qer[i].e);
        qer[i].idx=i;
    }
 
    sort(qer+1,qer+1+Q,sf);
 
 
    for(i=qer[1].s;i<=qer[1].e;i++)
    {
        if(cnt[arr[i]]==0) now++;
        cnt[arr[i]]++;
    }
    ans[qer[1].idx]=now;
    ll lf=qer[1].s;
    ll rf=qer[1].e;
    //for(j=1;j<=5;j++)
    //        printf("%lld ",cnt[j]);
    //    printf("\n");
 
    for(i=2;i<=Q;i++)
    {    
        if(qer[i].s<lf) pl(qer[i].s,lf-1);
        if(qer[i].e>rf) pl(rf+1,qer[i].e);
        if(qer[i].s>lf) mi(lf,qer[i].s-1);
        if(qer[i].e<rf) mi(qer[i].e+1,rf);
 
        lf=qer[i].s;
        rf=qer[i].e;
        ans[qer[i].idx]=now;
        //for(j=1;j<=5;j++)
        //    printf("%lld ",cnt[j]);
        //printf("\n");
    }
 
    for(i=1;i<=Q;i++)
        printf("%lld\n",ans[i]);
}