구간 최빈 빈도
다이아몬드 IV의견: 0
길이 \(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\)가 주어진다.
각 질의에 대해 해당 구간의 최빈값 빈도를 한 줄에 하나씩 출력한다.
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.
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
평가 및 의견
구간 최빈 빈도
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 최빈 빈도