Mo's (2) 썸네일형 리스트형 백준 12986 - 화려한 마을 2 https://www.acmicpc.net/problem/12986 $O((N+Q)\sqrt N \log N)$ 솔루션 - Mo's + Indexed heap Mo's 알고리즘 적용을 위해 쿼리를 정렬한다. 그리고 -100000부터 100000까지의 값을 index로 취급하면 가장 많이 출연한 원소의 횟수를 indexed heap로 찾을 수 있다. 그러면 각 쿼리를 처리하면서 원소의 출연 횟수를 구역을 횡단할 때마다 $O(\log N)$의 시간 복잡도로 갱신하게 되고 쿼리의 답은 max indexed heap의 top이 된다. 시간 복잡도 : $O((N+Q)\sqrt N \log N)$ 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22.. 백준 13548 - 수열과 쿼리 6 https://www.acmicpc.net/problem/13548 모스 알고리즘의 연습 문제 중 하나이다. $O((N + M) \sqrt M)$으로 처리를 하되, 다음을 이용해야 한다. 포인터가 한 index 움질일 때마다 구간에 속한 수의 출현 빈도의 변화량 d는 $-1 \leq d \leq 1$ 이므로 $O(1)$에 출현 횟수의 변화를 계산할 수 있다. 이를 구현하기 위해 어떤 수를 index로 하여 그 출현 횟수를 저장하는 배열 mp와 어떤 출현 횟수를 index로 하여 그 출현 횟수의 횟수를 저장하는 배열 counter를 둔다. 이렇게 되면 구간이 1씩 길어질 때마다 새로 포함된 값 x를 mp에 반영하기 전에 기존 구간에서 x의 출현 횟수를 저장한 counter를 바꿔줘야 한다. counter의.. 이전 1 다음
