Elearning CodePath – CTP Online Judge

RANGECOUNT

Mã bài: RANGECOUNT

Tên bài: RANGECOUNT

## Đề bài

Cho một dãy số nguyên $A$ gồm $n$ phần tử, các phần tử được đánh số từ $1$ đến $n$.

Có $q$ truy vấn, mỗi truy vấn gồm ba số nguyên $l, r, k$. Với mỗi truy vấn, hãy đếm số phần tử trong đoạn từ vị trí $l$ đến vị trí $r$ có giá trị nhỏ hơn hoặc bằng $k$.

Nói cách khác, với mỗi truy vấn $(l, r, k)$, cần tính số lượng chỉ số $i$ thỏa mãn:

$l \le i \le r$ và $A_i \le k$

## Dữ liệu vào

Dữ liệu vào từ file `RANGECOUNT.INP`.

## Dữ liệu ra

Ghi ra file `RANGECOUNT.OUT`.

## Ví dụ 1

| `RANGECOUNT.INP` | `RANGECOUNT.OUT` |
| :-- | :-- |
| `5 4` `1 3 2 5 4` `1 5 3` `2 4 4` `3 5 2` `1 3 0` | `3` `2` `1` `0` |

## Giải thích ví dụ 1

| Truy vấn | Các phần tử trong đoạn | Điều kiện | Kết quả |
| :-- | :-- | :-- | :-- |
| `1 5 3` | $1, 3, 2, 5, 4$ | Các phần tử $\le 3$ là $1, 3, 2$ | $3$ |
| `2 4 4` | $3, 2, 5$ | Các phần tử $\le 4$ là $3, 2$ | $2$ |
| `3 5 2` | $2, 5, 4$ | Các phần tử $\le 2$ là $2$ | $1$ |
| `1 3 0` | $1, 3, 2$ | Không có phần tử nào $\le 0$ | $0$ |

## Ví dụ 2

| `RANGECOUNT.INP` | `RANGECOUNT.OUT` |
| :-- | :-- |
| `6 5` `-5 10 0 -2 7 -5` `1 6 -5` `1 4 -1` `2 5 7` `3 6 0` `4 4 -3` | `2` `2` `2` `3` `0` |

## Giải thích ví dụ 2

| Truy vấn | Các phần tử trong đoạn | Điều kiện | Kết quả |
| :-- | :-- | :-- | :-- |
| `1 6 -5` | $-5, 10, 0, -2, 7, -5$ | Các phần tử $\le -5$ là $-5, -5$ | $2$ |
| `1 4 -1` | $-5, 10, 0, -2$ | Các phần tử $\le -1$ là $-5, -2$ | $2$ |
| `2 5 7` | $10, 0, -2, 7$ | Các phần tử $\le 7$ là $0, -2, 7$ | $3$ |
| `3 6 0` | $0, -2, 7, -5$ | Các phần tử $\le 0$ là $0, -2, -5$ | $3$ |
| `4 4 -3` | $-2$ | Không có phần tử nào $\le -3$ | $0$ |

## Giới hạn

| Subtask | Ràng buộc | Điểm |
| :-- | :-- | :-- |
| 1 | $n, q \le 2000$ | $30\%$ |
| 2 | $n, q \le 10^5$ | $70\%$ |

Với mọi test:

$1 \le n, q \le 10^5$

$|A_i|, |k| \le 10^9$

$1 \le l \le r \le n$

✅ Đã AC: 1 / 1 submissions