수열과 쿼리 6 [BOJ 13548]

티어가 하나 낮은 수열과 쿼리 5의 풀이를 확장한다. 수쿼 5를 아직 안 풀었다면 이 문제와 같이 푸는 것을 추천한다. 아래는 수열과 쿼리 5의 풀이가 담긴 링크이다.

https://unorderedmap.tistory.com/28

수열과 쿼리 5 [BOJ 13547]

 

문제 요약

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

i j : 구간 [i, j]에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다.

 

사용 알고리즘

Mo's Algorithm

 

풀이

수열과 쿼리 5를 풀 때 Mo's Algorithm을 사용하여 해당 구간에 어떤 수가 몇 개 존재하는지를 배열을 통해 관리할 수 있음을 알았다.

여기서 약간 관점을 돌려, 어떤 수의 출현 횟수를 담는 수열을 만들자. 예를 들어, 1 2 3 3 3 이라는 기존 수열이 있으면, 각 수의 개수를 담아 1 1 3 이라는 새로운 수열을 만드는 것이다. 만약 여기서 2가 하나 추가된다면 기존 수열은 1 2 2 3 3 3 이 될텐데, 새로운 수열에서는 출현 횟수가 1이었던 수가 하나 제거되고 2였던 수가 하나 추가되었으므로 1 2 3 으로 만들 수 있다. 그렇다면 우리의 목적은 새로운 수열에서의 최댓값을 찾는 것이고, 이는 '새로운 수열에서 각 수가 몇 번 등장했는지'를 배열로 한 번 더 만들어주면 해결할 수 있다.

배열 C[i]는 '수열 A에서 i번 등장한 수들의 개수'이다. A에서 수가 추가될 때는 i를 제거하고 i+1을 추가하며, i+1이 기존 최댓값보다 크면 업데이트 한다. 감소할 때에는 C[i]가 0이 될 때를 찾아도 되지만, 쿼리 전이가 끝나고 나서 현재 최댓값부터 줄여나가며 C[i]가 0이 아닌 첫 지점을 찾아도 된다. 어차피 여기서 최댓값이 줄어드는 범위는 쿼리 전이에 사용한 이동의 수를 넘지 않기에, 시간복잡도에 영향을 주지 않는다.

이렇게 전체 시간복잡도 O(NsqrtN)에 문제를 해결할 수 있다.

 

코드

#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],C[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)
{
    C[B[A[x]]]--;
    B[A[x]]++;
    C[B[A[x]]]++;
    res=max(res,B[A[x]]);
}
void mo_dis(int x)
{
    C[B[A[x]]]--;
    B[A[x]]--;
    C[B[A[x]]]++;
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>N;
    sqrtN=sqrt(N),C[0]=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--);
        while(C[res]==0)res--;
        ans[Q[i].idx]=res;
    }
    for(int i=1;i<=M;i++)cout<<ans[i]<<'\n';
}

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장