Elearning CodePath – CTP Online Judge

Đếm số trong đoạn

TKM08_BSCOUNT

## Đề bài

Cho một dãy gồm `N` số nguyên `A1, A2, ..., AN`.

Có `Q` truy vấn. Mỗi truy vấn cho hai số nguyên `L` và `R`. Với mỗi truy vấn, hãy đếm có bao nhiêu phần tử của dãy nằm trong đoạn giá trị `[L, R]`, tức là thỏa mãn:

```text
L <= Ai <= R
```

## Dữ liệu vào

- Dòng đầu chứa hai số nguyên `N` và `Q`.
- Dòng thứ hai chứa `N` số nguyên `A1, A2, ..., AN`.
- `Q` dòng tiếp theo, mỗi dòng chứa hai số nguyên `L` và `R`.

## Dữ liệu ra

In ra `Q` dòng. Mỗi dòng là kết quả của một truy vấn theo đúng thứ tự xuất hiện.

## Ràng buộc

```text
1 <= N, Q <= 200000
-10^9 <= Ai, L, R <= 10^9
L <= R
```

## Subtask

- Subtask 1 — 25 điểm: `N, Q <= 50`.
- Subtask 2 — 35 điểm: `N, Q <= 5000`.
- Subtask 3 — 40 điểm: Không có ràng buộc bổ sung.

## Ví dụ

### Input

```text
5 4
1 5 2 2 10
1 2
3 9
2 2
-5 100
```

### Output

```text
3
1
2
5
```

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

Dãy sau khi sắp xếp là `1 2 2 5 10`.

- Đoạn `[1, 2]` chứa `1, 2, 2`, có `3` số.
- Đoạn `[3, 9]` chứa `5`, có `1` số.
- Đoạn `[2, 2]` chứa hai số `2`.
- Đoạn `[-5, 100]` chứa toàn bộ `5` số.

✅ Đã AC: 1 / 6 submissions