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