[백준 23238번] Best Student

참고 : 풀이 코드는 없습니다. 힌트만 드립니다.

 

1. Mo's -> Query sort, delete, add

2. Student ID -> 값 / 좌표 압축

3. 압축된 값의 범위가 1 ~ 10만이고, 그 값을 SQRT 로 나눔 (SQRT Decomposition)

4. SQRT 로 나눈 버킷마다 빈도수의 MAX 값 저장

5. 쿼리에 대한 답은 모든 버킷에서 빈도수의 MAX 값을 가진 버킷을 찾음. 버킷을 찾았으면 그 안에서 MAX 값을 또 찾아줌. 빈도수가 같은 값이 있으면 ID 가 더 큰 값을 찾음. O(Q) * O(sqrt + sqrt)

(값 / 좌표 압축을 할 때 정렬을 해서 실제 값이 크면, 압축된 값도 크도록 해주면 구현이 편해짐)

 

시간복잡도 O(Q * sqrt)