BOJ 2912 : 백설공주와 난쟁이

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

사전 지식 / 관련 알고리즘 : Mo's Algorithm

 

* Mo's Algorithm 을 모르신다면, 위 링크를 먼저 접속하시는 것을 추천 드립니다.

 

 

또 하나의 전형적인 Mo's Algorithm 문제다.

마찬가지로, 정렬 후 첫 쿼리는 수동으로 구한다.

 

ncnt[i] : i 번 색 모자를 쓰고 있는 난쟁이의 수

ex) ncnt[3] = 5 는, 3번 색 모자를 5명의 난쟁이가 쓰고 있다는 것입니다.

 

ccnt[i] : ncnt[k]=i 를 만족하는 k 의 개수

ex) ccnt[4] = 3 은, 그 색깔의 모자를 쓰고 있는 난쟁이가 정확히 4명인 색깔이, 정확히 3종류 있다는 것입니다. 

 

ncnt 와 ccnt 를 통해, 현재 가장 많이 사용된 모자 색의 개수를 파악할 수 있습니다.

* ans = 가장 많이 쓰고 있는 모자의 개수

void ins(int idx){ // idx 번째 난쟁이가 추가된다.
    int num = arr[idx]; /// num 색 모자가 1개 추가된다.
    ccnt[ncnt[num]]--;
    ncnt[num]++; ccnt[ncnt[num]]++;
    if(ans < ncnt[num]) ans = ncnt[num];
}

void erse(int idx){ // idx 번째 난쟁이가 제거된다.
    int num = arr[idx]; // num 색 모자가 1개 없어진다. 
    ccnt[ncnt[num]]--;
    if(ccnt[ncnt[num]]==0 && ans==ncnt[num]) ans--; // 중요!
    ncnt[num]--; ccnt[ncnt[num]]++;
}

 

idx 번째 난쟁이를 추가하고 제거하는 함수는 위와 같다.

* 특히 erse 함수의 3번째 줄이 중요한데, 이해가 가지 않는 부분은 질문해주세요 !

 

이 두 함수만 있다면, 그 이후는 그냥 전형적인 Mo's Algorithm 구현이다.

 

 

 

#include <bits/stdc++.h>
using namespace std;

int ncnt[10010]; /// 각 수가 몇 번 등장?
int ccnt[300010]; /// 각 수의 cnt 가 몇 번 등장?
int n, c, m, sq, arr[300010], ans;
pair <int, int> dap[10010]; /// (0, .) : 불만족, (1, x) : 1이고 답이 x

struct query{
    int s, e, L, ID;
    bool operator<(const query &r)const{
        if(e/sq == r.e/sq) return s<r.s;
        return e/sq < r.e/sq;
    }
}q[10010];

void ins(int idx){
    int num = arr[idx]; /// num 삽입
    ccnt[ncnt[num]]--;
    ncnt[num]++; ccnt[ncnt[num]]++;
    if(ans < ncnt[num]) ans = ncnt[num];
}

void erse(int idx){
    int num = arr[idx]; /// num 제거
    ccnt[ncnt[num]]--;
    if(ccnt[ncnt[num]]==0 && ans==ncnt[num]) ans--;
    ncnt[num]--; ccnt[ncnt[num]]++;
}

int main(){
    int i, j, L, R;
    scanf("%d%d", &n, &c); sq = int(sqrt(n));
    for(i=1;i<=n;i++)scanf("%d", &arr[i]);
    scanf("%d", &m);
    for(i=1;i<=m;i++){
        q[i].ID = i;
        scanf("%d%d", &q[i].s, &q[i].e);
        q[i].L = q[i].e - q[i].s + 1;
    }
    sort(q+1, q+m+1);

    /// 1st query
    for(i=q[1].s;i<=q[1].e;i++) ins(i);
    if(ans > q[1].L / 2){
        for(j=1;j<=c;j++)if(ncnt[j] == ans){
            dap[q[1].ID] = {1, j};
            break;
        }
    }
    else dap[q[1].ID] = {0, 0};

    /// 2~mth queries
    L = q[1].s, R = q[1].e;
    for(i=2;i<=m;i++){
        while(L < q[i].s) erse(L++);
        while(L > q[i].s) ins(--L);
        while(R < q[i].e) ins(++R);
        while(R > q[i].e) erse(R--);
        if(ans > q[i].L / 2){
            for(j=1;j<=c;j++)if(ncnt[j] == ans){
                dap[q[i].ID] = {1, j};
                break;
            }
        }
        else dap[q[i].ID] = {0, 0};
    }

    for(i=1;i<=m;i++){
        if(dap[i].first) printf("yes %d\n", dap[i].second);
        else printf("no\n");
    }
}