구간에서 k 이하인 원소의 개수
플래티넘 V의견: 0
길이 \(n\) 인 정수 배열 \(a_1, a_2, \dots, a_n\) 이 주어진다. 이어서 \(q\) 개의 질의가 주어지며, 각 질의는 세 정수 \(l, r, k\) 로 이루어진다.
각 질의에 대하여, 구간 \(a_l, a_{l+1}, \dots, a_r\) 안에서 값이 \(k\) 이하인 원소의 개수를 구하여라.
모든 질의는 처음부터 주어지므로 오프라인으로 처리할 수 있다. 머지 소트 트리나 Mo's 알고리즘으로 풀 수 있다.
\(1 \le n, q \le 10^5\)
\(-10^9 \le a_i, k \le 10^9\)
\(1 \le l \le r \le n\)
첫째 줄에 두 정수 \(n\) 과 \(q\) 가 공백으로 구분되어 주어진다.
둘째 줄에 \(n\) 개의 정수 \(a_1, \dots, a_n\) 이 주어진다.
다음 \(q\) 개의 줄에 각각 세 정수 \(l, r, k\) 가 주어진다 (\(1 \le l \le r \le n\)).
각 질의의 답을 입력 순서대로 한 줄에 하나씩 출력한다.
8 3
3 1 4 1 5 9 2 6
1 8 4
1 4 1
3 6 5
5
2
3
첫 질의는 \(a_{1..8}\) 에서 \(4\) 이하인 값 \(\{3,1,4,1,2\}\) 의 개수이므로 \(5\). 둘째 질의는 \(a_{1..4}=[3,1,4,1]\) 중 \(1\) 이하인 \(\{1,1\}\) 로 \(2\). 셋째 질의는 \(a_{3..6}=[4,1,5,9]\) 중 \(5\) 이하인 \(\{4,1,5\}\) 로 \(3\).
1 2
7
1 1 7
1 1 6
1
0
원소가 하나뿐이다. \(7 \le 7\) 이므로 첫 답은 \(1\), \(7 \le 6\) 은 거짓이므로 둘째 답은 \(0\).
riseoj 작성
출처 Original
평가 및 의견
구간에서 k 이하인 원소의 개수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간에서 k 이하인 원소의 개수