BOJ 13548 - 수열과 쿼리 6

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

문제 태그

Mo's algorithm

문제 소개

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

• i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다.

문제 풀이

일단 문제를 읽어보자. 구간 내에서 가장 많이 나타나는 수 -> 각각의 수들이 몇번씩 나왔는지 관리하려고 하면 된다. 또한 이 질문이 쿼리로 주어진다. 이러한 형식의 문제를 많이 풀어봤으면 바로 Mo's algorithm을 써야 한다는 생각을 할 수 있다.

Mo's algorithm 으로 구간을 더하거나 빼주면서 각 숫자별로 몇 개씩 있는지 관리한다고 생각해보자. 각 쿼리에 맞는 구간에 도달할 때마다 우리는 쿼리에 대한 답을 내야한다. 하지만 가장 많이 있는 갯수를 알기 위해서는 모든 숫자에 대해서 그 갯수를 보면서 가장 높은 값을 찾아야 한다. 이 과정에서 시간복잡도는 수의 범위 K에 대해 $O(K)$이 걸리게 되고 이로인해 시간초과가 발생한다. 따라서 우리는 답을 더 빠른시간에 낼 수 있는 방법을 찾아야 한다. 

이때 가장 먼저 생각할 부분은 구간을 바꿔주는 과정에서 좀 더 많은 값들을 처리하는 것이다. 여기서 한가지 아이디어를 생각해야 한다. Mo's는 수의 집합을 관리하는 데 굉장히 좋은 알고리즘이기 때문에, 다른 수를 관리하자는 것이다. ccnt[i]=(cnt[k]=i인 k의 갯수)로 정의하고 관리한다. 즉 ccnt[3]=5이면, 구간내에서 3번 등장하는 수가 5종류가 있다는 것이다. 

이 값을 이용하여 답을 관리할 수 있는지 생각해보자. 구간을 더할때는 ccnt[x]가 1 감소하고 ccnt[x+1]이 하나 증가하는 과정이 반복될 것이다. 이 과정에서 전에 도달하지 못했던 ccnt 위치에 처음 도달하게 된다면 답은 그 숫자가 될 것이다. 또한 구간을 뺄때는 ccnt[x]가 1 감소하고 ccnt[x-1]이 하나 증가하는 과정이 반복될 것이다. 이과정에서 원래 답이 x였는데 ccnt[x]가 0이 된다면 답은 x-1로 1이 감소할 것이다. 따라서 답을 같이 관리할 수 있게 된다. 

ccnt[i]=(cnt[k]=i인 k의 갯수)로 정의하고 이 값도 같이 관리하면서 진행해야한다는 아이디어를 생각하는 것이 핵심인 문제였다. 

코드

#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 ccnt[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++)
    {
        ccnt[cnt[arr[i]]]--;
        cnt[arr[i]]--;
        ccnt[cnt[arr[i]]]++;
        if(ccnt[now]==0) now--;
    }
}
 
void pl(ll s, ll e)
{
    ll i;
    for(i=s;i<=e;i++)
    {
        ccnt[cnt[arr[i]]]--;
        cnt[arr[i]]++;
        ccnt[cnt[arr[i]]]++;
        now=max(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);
 
    ccnt[0]=n;
    for(i=qer[1].s;i<=qer[1].e;i++)
    {
        ccnt[cnt[arr[i]]]--;
        cnt[arr[i]]++;
        ccnt[cnt[arr[i]]]++;
        now=max(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]);
}