플래티넘 I설명
길이 \(N\)의 정수 수열 \(A_1, \dots, A_N\)이 주어진다. \(Q\)개의 질의가 주어지며, 각 질의는 구간 \([l, r]\)로 표현된다.
각 질의에 대해 부분 수열 \(A_l, A_{l+1}, \dots, A_r\)에서 가장 많이 등장하는 값의 등장 횟수(최빈값의 빈도)를 출력하여라.
구간 최빈값 빈도는 차분이 어려워 단순 세그먼트 트리로는 합치기가 되지 않는다.
제약
\(1 \le N, Q \le 50{,}000\)
\(1 \le l \le r \le N\)
\(|A_i| \le 10^9\)
입력 형식
첫 줄에 두 정수 \(N\), \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, \dots, A_N\)이 주어진다.
이어서 \(Q\)개의 줄에 각 질의의 \(l\), \(r\)가 주어진다.
출력 형식
각 질의에 대해 해당 구간의 최빈값 빈도를 한 줄에 하나씩 출력한다.
예제 1
입력
7 4
1 2 2 3 2 1 1
1 7
2 4
5 7
1 1
출력
3
2
2
1설명
[1,2,2,3,2,1,1] 전체: 2가 3번으로 최빈 -> 3. [2,2,3]: 2가 2번 -> 2. [2,1,1]: 1이 2번 -> 2. [1]: 1번 -> 1.
예제 2
입력
3 3
5 5 5
1 3
1 2
2 2
출력
3
2
1설명
모두 같은 값. [1,3]은 3번, [1,2]는 2번, [2,2]는 1번.
문제 정보
riseoj 작성
출처 Original
태그
