Elearning CodePath – CTP Online Judge

TRUYVAN

🟢 Easy #Segment Tree #Fenwick Tree

## Đề bài

Một siêu thị quản lý các mặt hàng đang kinh doanh bằng phần mềm trên máy tính. Nhân viên trong siêu thị cần cập nhật giá bán của các mặt hàng. 
Giá bán được tính theo đơn vị nghìn đồng. Danh sách giá bán thay đổi liên tục khi siêu thị nhập thêm mặt hàng mới hoặc ngừng kinh doanh một mặt hàng. 
Ban quản lý thường xuyên cần truy vấn mức giá thấp thứ $k$ trong danh sách hiện tại.

Quy tắc xếp hạng như sau:

- Các mặt hàng có cùng giá được xếp cùng một mức.
- Mức tiếp theo được tính bằng số mức giá phân biệt thấp hơn nó cộng $1$.

Yêu cầu: Xử lý $n$ mặt hàng ban đầu và $q$ thao tác theo thứ tự. 
Với mỗi thao tác truy vấn `Q k`, hãy cho biết mức giá thấp thứ $k$ theo thứ hạng trong danh sách hiện tại. 
Nếu $k$ lớn hơn số mức giá phân biệt hiện có, kết quả truy vấn là $0$.

## Dữ liệu vào

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

| Dòng | Mô tả |
| :-- | :-- |
| 1 | Chứa số nguyên dương $n$ là số mặt hàng ban đầu |
| 2 | Chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ là giá của các mặt hàng ban đầu |
| 3 | Chứa số nguyên dương $q$ là số thao tác |
| $q$ dòng tiếp theo | Mỗi dòng chứa một thao tác thuộc một trong ba dạng `A x`, `D x`, `Q k` |

Ý nghĩa các thao tác:

| Thao tác | Ý nghĩa |
| :-- | :-- |
| `A x` | Nhập thêm một mặt hàng có giá $x$ vào danh sách |
| `D x` | Loại bỏ một mặt hàng có giá $x$ ra khỏi danh sách hiện tại. Nếu có nhiều mặt hàng cùng giá $x$, chỉ xóa một mặt hàng. Nếu không tồn tại mặt hàng nào có giá $x$, bỏ qua thao tác |
| `Q k` | Truy vấn mức giá thấp thứ $k$ theo thứ hạng |

## Dữ liệu ra

Ghi ra file `TRUYVAN.OUT`.

## Ví dụ

| `TRUYVAN.INP` | `TRUYVAN.OUT` |
| :-- | :-- |
| `4` `5 3 3 7` `8` `Q 1` `Q 2` `A 4` `Q 2` `D 3` `D 3` `Q 2` `Q 6` | `3` `5` `4` `5` `0` |

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

Ban đầu danh sách giá là $5, 3, 3, 7$.

| Thao tác | Kết quả | Giải thích |
| :-- | :-- | :-- |
| `Q 1` | $3$ | Các mức giá phân biệt là $3, 5, 7$, mức thấp thứ $1$ là $3$ |
| `Q 2` | $5$ | Mức thấp thứ $2$ là $5$ |
| `A 4` | | Danh sách trở thành $5, 3, 3, 7, 4$ |
| `Q 2` | $4$ | Các mức giá phân biệt là $3, 4, 5, 7$, mức thấp thứ $2$ là $4$ |
| `D 3` | | Xóa một mặt hàng có giá $3$ |
| `D 3` | | Xóa tiếp một mặt hàng có giá $3$ |
| `Q 2` | $5$ | Các mức giá phân biệt là $4, 5, 7$, mức thấp thứ $2$ là $5$ |
| `Q 6` | $0$ | Không tồn tại mức giá thấp thứ $6$ |

## Giới hạn

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

✅ Đã AC: 2 / 9 submissions