수열과 쿼리 1

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

요약
정적인 수열이 주어질 때, 각 질의마다 A[i..j] 범위에서 k보다 큰 값의 개수를 세어 출력합니다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 정렬, 이분 탐색, 분할 정복
정답자
아직 제출이 없습니다

문제

길이가 NN인 수열 A1,A2,…,ANA_1, A_2, \dots, A_N이 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

  • i j k: Ai,Ai+1,…,AjA_i, A_{i+1}, \dots, A_j 중에서 kk보다 큰 원소의 개수를 출력한다.

입력

첫째 줄에 수열의 크기 NN이 주어진다. (1≤N≤1000001 \le N \le 100000)

둘째 줄에 A1,A2,…,ANA_1, A_2, \dots, A_N이 공백으로 구분되어 주어진다. (1≤Ai≤1091 \le A_i \le 10^9)

셋째 줄에 쿼리의 개수 MM이 주어진다. (1≤M≤1000001 \le M \le 100000)

넷째 줄부터 MM개의 줄에 쿼리가 한 줄에 하나씩 ii, jj, kk 순서로 주어진다. (1≤i≤j≤N1 \le i \le j \le N, 1≤k≤1091 \le k \le 10^9)

출력

각 쿼리의 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

예제7

  1. 예제 1

    입력
    5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
    예상 출력
    2
0
3

  2. 예제 2

    입력
    1
1
3
1 1 1
1 1 1000000000
1 1 1
    예상 출력
    0
0
0

  3. 예제 3

    입력
    6
7 7 7 7 7 7
5
1 6 6
1 6 7
1 6 8
3 3 7
2 5 1
    예상 출력
    6
0
0
0
4

  4. 예제 4

    입력
    5
1000000000 1 1000000000 1 1000000000
6
1 5 999999999
1 5 1000000000
1 5 1
2 4 999999999
5 5 999999999
1 1 1000000000
    예상 출력
    3
0
3
1
1
0

  5. 예제 5

    입력
    20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
1 20 1
1 20 2
1 20 3
1 20 4
1 20 5
1 20 6
1 20 7
1 20 8
1 20 9
1 20 10
1 20 11
1 20 12
1 20 13
1 20 14
1 20 15
1 20 16
1 20 17
1 20 18
1 20 19
1 20 20
    예상 출력
    19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

  6. 예제 6

    입력
    20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
20
1 20 10
2 20 10
3 20 10
4 20 10
5 20 10
6 20 10
7 20 10
8 20 10
9 20 10
10 20 10
11 20 10
12 20 10
13 20 10
14 20 10
15 20 10
16 20 10
17 20 10
18 20 10
19 20 10
20 20 10
    예상 출력
    10
9
8
7
6
5
4
3
2
1
0
0
0
0
0
0
0
0
0
0

  7. 예제 7

    입력
    12
3 3 2 2 2 1 3 4 5 5 2 2
15
9 9 3
1 8 2
4 12 4
3 8 3
2 3 5
5 12 2
4 7 1
2 5 6
9 12 5
12 12 1
12 12 6
6 12 1
2 11 4
2 10 1
5 12 6
    예상 출력
    1
4
2
1
0
4
3
0
0
1
0
6
2
8
0