[BOJ 2912] 백설공주와 난쟁이

https://www.acmicpc.net/problem/2912

2912번: 백설공주와 난쟁이

Tag : random, mo's, merge sort tree

 

문제요약

쿼리마다 구간의 크기/2 보다 많은 비중을 차지하는 색이 있으면 

yes + 색을 출력하고 없으면 no를 출력하는 문제다.

 

풀이

매우 다양한 풀이가 존재한다.

머지소트트리, mo's, 랜덤... 등

mo's는 \(O((N + M) \times N^{\frac{1}{2}} + M \times C)\)

랜덤은 \(O(k N log N)\) (k는 랜덤을 돌려볼 적당한 상수다)

 

랜덤 풀이는 다음과 같다.

1. 각 색마다의 인덱스를 저장한다.

2. 쿼리마다 k번씩 구간의 아무 원소나 집어보고 \((r - l + 1) / 2\)보다 많이 등장하는지 이분탐색으로 구한다.

3. 찾으면 yes 아니면 no

 

구간에 과반수를 넘기는 색이 존재한다면 랜덤으로 뽑았을 때 그것이 답일 확률은 \(1/2\)이상이다. 

따라서 이것을 k번 반복해본다면 구간에 답이 있는데 못찾을 확률은 \(1/(2^k)\)이하이다.

대충 15번만 돌려도 이 확률이 말도 안되게 작기 때문에 잘 돌아간다.

 

+ 1등먹었다

 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

struct RAND {
    random_device rg;
    mt19937 rd;
    RAND() { rd.seed(rg()); }
    int nxt(int l = 0, int r = 32767) { return uniform_int_distribution<int>(l, r)(rd); }
} rnd;

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
int z[36];
char*c=(char*)mmap(0,z[12],1,2,0,fstat(0,(struct stat *)z));
inline int f(){int x=0;bool e;c+=e=*c=='-';while(*c>='0')x=10*x+*c++-'0';c++;return e?-x:x;}
char O[2000000],*d=O;
template<class T> inline void p(T x) {
    if(x<0) *d++='-', x=-x;
    char t[16], *q=t;
    do *q++=x%10|48; while(x/=10);
    do *d++=*--q; while(q!=t);
    *d++=10;
}

int a[303030];
vector<int> idx[10101];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n = f(), c = f();
    for(int i=1; i<=n; i++) {
        a[i] = f();
        idx[a[i]].emplace_back(i);
    }
    int m = f();
    while(m--) {
        int l = f(), r = f();
        int f = 0;
        for(int i=0; i<15; i++) {
            int x = rnd.nxt(l, r);
            int lo = lower_bound(idx[a[x]].begin(), idx[a[x]].end(), l) - idx[a[x]].begin();
            int hi = upper_bound(idx[a[x]].begin(), idx[a[x]].end(), r) - idx[a[x]].begin();
            int cnt = hi - lo;
            if(cnt > (r - l + 1) / 2) {
                f = a[x];
                break;
            }
        }
        if(f) {
            *d++ = 'y';
            *d++ = 'e';
            *d++ = 's';
            *d++ = 32;
            p(f);
        } else {
            *d++ = 'n';
            *d++ = 'o';
            *d++ = 10;
        }
    }
    write(1, O, d - O);
}