배열 전체 탐색하기

면접 대비

시간 제한1초메모리 제한512 MB

요약

배열 A와 m개의 질의가 주어질 때, A의 원소 중 k 이상인 것, k보다 큰 것, i 이상 j 이하인 것의 개수를 각각 구한다.

난이도: 보통10점 중 4점
유형: 이분 탐색, 정렬, 배열, 누적 합
정답자: 아직 제출이 없습니다

문제

크기 n인 정수형 배열 A가 주어진다. 배열 A의 원소는 A[0], A[1], ... , A[n-1]이다. 배열 A에는 같은 값을 갖는 원소가 여러 개 존재할 수 있다. 배열 A에 대한 m개의 질의가 저장된 배열 B가 주어진다. 배열 B에 저장된 m개의 질의는 아래 세 가지 유형으로 구분된다. 첫 번째가 유형 1, 두 번째가 유형 2, 세 번째가 유형 3이다.

1 k: 배열 A의 원소 중 k보다 크거나 같은 원소의 개수를 출력한다.
2 k: 배열 A의 원소 중 k보다 큰 원소의 개수를 출력한다.
3 i j: 배열 A의 원소 중 i보다 크거나 같고 j보다 작거나 같은 원소의 개수를 출력한다.

배열 B에 저장된 첫 번째 질의부터 m번째 질의까지 순서대로 처리하면서 질의 결과를 출력하자.

입력

첫 번째 줄에 n과 m이 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄에 배열 A의 원소 A[0], A[1], ... , A[n-1]이 공백을 사이에 두고 순서대로 주어진다.

세 번째 줄부터 m개의 줄에 걸쳐 배열 B에 저장된 m개의 질의가 순서대로 주어진다. 한 줄에 하나의 질의를 나타내는 정수가 공백을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄부터 질의 결과를 순서대로 한 줄씩 출력한다.

제한

1 ≤ n, m ≤ 100,000
1 ≤ A[i] ≤ 1018 (0≤ i ≤ n - 1)
1 ≤ i ≤ j ≤ 1018
1 ≤ k ≤ 1018

예제2

예제 1

입력

8 15
1 3 5 7 9 11 13 15
1 2
1 4
1 6
1 8
1 20
2 2
2 4
2 6
2 8
2 20
3 2 10
3 4 4
3 6 13
3 8 13
3 20 30

예상 출력

예제 2

입력

8 15
2 2 5 5 5 10 15 20
1 1
1 2
1 3
1 5
1 30
2 1
2 2
2 3
2 5
2 30
3 1 5
3 2 5
3 3 13
3 5 10
3 30 30

예상 출력