구간 최대 빈도가중값
다이아몬드 III의견: 0
길이 \(N\)의 수열 \(a_1, a_2, \dots, a_N\)이 주어진다. \(Q\)개의 질의가 주어지며, 각 질의는 구간 \([l, r]\)이다.
각 질의에 대해, 구간 \(a_l, \dots, a_r\)에 등장하는 각 서로 다른 값 \(v\)에 대해 그 등장 횟수 \(f\)를 곱한 값 \(v \cdot f\) 중 최댓값을 출력하여라.
구간을 늘릴 때(원소 추가)는 빈도와 최댓값을 쉽게 갱신할 수 있지만, 줄일 때(원소 제거)는 최댓값을 되돌리기 어렵다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le a_i \le 10^9\)
\(1 \le l \le r \le N\)
첫 줄에 수열의 길이 \(N\)과 질의 수 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
다음 \(Q\)개의 줄에 각 질의의 \(l\), \(r\)이 주어진다.
각 질의에 대해 \(\max_v (v \cdot f_v)\)를 한 줄에 하나씩 출력한다.
6 3
1 2 2 3 3 3
1 6
2 3
4 6
9
4
9전체 [1..6]: 값3이 3번 등장해 \(3\times3=9\)가 최대. 구간 [2,3]은 값2가 2번 \(=4\). 구간 [4,6]은 값3이 3번 \(=9\).
4 2
5 5 5 5
1 4
1 1
20
5모두 5. 전체 구간은 \(5\times4=20\), 한 칸은 \(5\times1=5\).
riseoj 작성
출처 Original
평가 및 의견
구간 최대 빈도가중값
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 최대 빈도가중값