Elearning CodePath – CTP Online Judge

BIT Quản lý Tập hợp

ORDSET

🟢 Easy #Segment Tree #Fenwick Tree

### 📌 Thông tin chung

---
### 📝 Bài toán

Bạn cần quản lý một tập hợp động $S$ hỗ trợ hai thao tác cơ bản và hai loại truy vấn:

* **Thao tác 1 (INSERT(S, x))**: Nếu $x$ không thuộc $S$, thêm $x$ vào $S$.
* **Thao tác 2 (DELETE(S, x))**: Nếu $x$ thuộc $S$, xóa $x$ khỏi $S$.
* **Truy vấn 1 (K-TH(S, k))**: Trả về số bé thứ $k$ của $S$. Nếu $k$ lớn hơn số phần tử của $S$, in ra `'invalid'`.
* **Truy vấn 2 (COUNT(S, x))**: Đếm số lượng số thuộc $S$ bé hơn $x$.

---
### 📥 Định dạng Đầu vào

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

* Dòng 1: Ghi số nguyên dương $Q$ - số thao tác.
* $Q$ dòng sau: Mỗi dòng chứa một ký tự (`I`, `D`, `K` hoặc `C`) và một số nguyên là tham số cho thao tác đó.
    * Nếu tham số là giá trị $x$, dữ liệu đảm bảo $|x| \le 10^9$.
    * Nếu tham số là chỉ số $k$ (cho truy vấn K-TH), dữ liệu đảm bảo $1 \le k \le 10^9$.

Giới hạn:
* $1 \le Q \le 2 \times 10^5$.
* Giá trị $x$ và chỉ số $k$ có thể rất lớn ($10^9$).

---
### 📤 Định dạng Đầu ra

Ghi ra file `ORDSET.OUT`. Với mỗi truy vấn (`K` hoặc `C`), in kết quả trên một dòng. Với truy vấn K-TH, nếu $k$ lớn hơn số phần tử của $S$, in ra `'invalid'`.

---
### ✨ Ví dụ

---
### 🏷  Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $Q \le 5000$, $|x| \le 1000$ | $40\%$ |
| 2 | $Q \le 2 \times 10^5$, $|x| \le 10^9$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions