Elearning CodePath – CTP Online Judge

Kho số thứ k

kthfreq

Ban đầu kho số rỗng.  
Có `q` thao tác:

```text
+ x
```

Thêm số `x` vào kho.

```text
- x
```

Xóa một lần xuất hiện của số `x` khỏi kho. Dữ liệu đảm bảo số `x` đang tồn tại.

```text
? k
```

In ra số nhỏ thứ `k` trong kho hiện tại. Dữ liệu đảm bảo kho có ít nhất `k` phần tử.

Các giá trị luôn nằm trong đoạn `1..M`.

## Input

```text
M q
q dòng thao tác
```

## Output

Với mỗi thao tác `?`, in đáp án trên một dòng.

## Subtasks

| Subtask | Ràng buộc gợi ý | Điểm | Hướng làm |
|---|---:|---:|---|
| 1 | `q ≤ 200` | 20 | Lưu vector rồi sort |
| 2 | `M ≤ 5000` | 30 | Mảng tần suất + prefix |
| 3 | `M, q` lớn | 50 | Fenwick + tìm k-th |

## Ví dụ

### Input

```text
10 10
+ 5
+ 2
+ 8
? 2
+ 2
? 2
- 2
? 2
+ 10
? 4
```

### Output

```text
5
2
5
10
```

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

Sau ba lần thêm đầu tiên, kho là:

```text
{2, 5, 8}
```

Số nhỏ thứ `2` là `5`.

Sau khi thêm `2`, kho là:

```text
{2, 2, 5, 8}
```

Số nhỏ thứ `2` là `2`.

Sau khi xóa một số `2`, kho là:

```text
{2, 5, 8}
```

Số nhỏ thứ `2` là `5`.

Sau khi thêm `10`, kho là:

```text
{2, 5, 8, 10}
```

Số nhỏ thứ `4` là `10`.

✅ Đã AC: 0 / 0 submissions