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


N이 30만까지 가능하므로 O(N^2)으로는 도저히 1초 안에 나오기 힘듬. 게다가 메모리도 128MB로 생각보다 적음.

가장 처음 생각해볼 수 있는건 Sqrt decomposition. 쿼리당 시간복잡도 O(sqrt(N) log(N))에 해결할 수 있지만, 시간이 빡빡해서 왠지 안될 것 같다.


풀이 1.

구간에서 과반수인 수가 있으면, 내가 무작위로 수를 뽑을 때 과반수인 수가 뽑일 확률이 1/2 보다 크다.

따라서 해당 구간에서 70~80번 정도 뽑은 뒤, 구간에 해당 수가 몇 개 있는지 세본다. 이는 O(log N)에 가능하다.

따라서 쿼리당 O(K log N)으로 풀 수 있다. (K는 무작위로 뽑는 횟수)


풀이 2. (이거 이상함이거 맛다)

구간에서 과반수인 수가 있으면, 해당 구간의 서브구간들에서 가장 많이 포함된 수들을 생각해보면 그 중에 하나는 과반수인 수가 된다.

따라서 세그먼트 트리를 구성하여, 해당 구간 아래에서 가장 많이 가지고 있는 수를 보관해둔다.

이후 쿼리가 들어오면 해당 구간에 맞는 세그먼트 트리의 노드 O(log N)개를 확인하여, 각각의 수에 대해 쿼리 구간에 해당 수가 몇 개 있는지 세본다.

이는 O((log N)^2)에 가능하다.


풀이 3.

위의 아이디어를 응용해서, 세그먼트 트리에서 해당 구간에서 가장 많이 나온 색과, 해당 색 - 다른 색의 개수 를 저장해둔다.

이후 세그먼트 트리의 위로 올라갈 때 (구간을 합칠 때) 더 많은 쪽의 색, 개수는 (많은 쪽) - (적은 쪽)으로 저장한다.

이러면 쿼리가 들어오면 해당 구간에 해당되는 세그먼트 트리의 노드 O(log N)개를 확인한 이후, 이를 합쳐서 하나로 만들면, 단 하나의 색만 확인하면 된다.

따라서 쿼리당 O(log N)에 가능하다.


코드는 귀찮아서 풀이 1로 풀음.

코드: https://gist.github.com/0xrgb/533d3ef76ca1b0f3fd8d85ff6f391064