Elearning CodePath – CTP Online Judge

Xóa Xâu

GEN029

🟢 Medium #String #Greedy

---

### 📝 Bài toán

Cho xâu kí tự $S$ có $n$ kí tự chữ cái Latin viết in hoa 'A'..'Z'. Có $q$ lệnh xóa kí tự, mỗi lệnh xóa thuộc một trong 2 loại sau đây:

* **Loại 0:** Xóa 1 kí tự đầu tiên (tính từ trái qua phải) có thứ tự từ điển nhỏ nhất của xâu còn lại.
* **Loại 1:** Xóa 1 kí tự đầu tiên (tính từ trái qua phải) có thứ tự từ điển lớn nhất của xâu còn lại.

**Yêu cầu:** Tìm xâu kí tự còn lại sau khi thực hiện tuần tự $q$ lệnh xóa.

---

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

Vào từ file văn bản có thông tin sau:
* **Dòng đầu tiên** có 2 số nguyên dương $n, q$ $(n \le 2 \times 10^5; q \le 10^5)$.
* **Dòng thứ hai** là xâu kí tự $S$ chỉ có kí tự chữ cái Latin viết in hoa 'A'..'Z'.
* **Dòng thứ ba** có $q$ số, mỗi số là số $0$ hoặc số $1$ tương ứng thể hiện loại lệnh xóa.

Các số trên cùng một dòng trong file dữ liệu được viết cách nhau bởi dấu cách trống.

---

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

Ghi ra file kết quả xâu kí tự còn lại sau khi thực hiện tuần tự $q$ lệnh xóa.

---

### ✨ Ví dụ

| DỮ LIỆU VÀO | KẾT QUẢ RA | Giải thích |
| :---: | :---: | :--- |
| `10 4` `ADBAACDABC` `0 1 1 0` | `BACABC` | **Lần 1** (Loại 0): `ADBAACDA̲BC` → Xóa 'A' đầu tiên (nhỏ nhất) → `DBAACDA̲BC` **Lần 2** (Loại 1): `DBAACDA̲BC` → Xóa 'D' đầu tiên (lớn nhất) → `BAACDABC` **Lần 3** (Loại 1): `BAACDABC` → Xóa 'D' đầu tiên (lớn nhất) → `BAACABC` **Lần 4** (Loại 0): `BAACABC` → Xóa 'A' đầu tiên (nhỏ nhất) → `BACABC` |

**Giải thích chi tiết:**

Xâu ban đầu: `ADBAACDA̲BC`

1. **Lệnh 0** (xóa ký tự nhỏ nhất đầu tiên):
   - Ký tự nhỏ nhất: 'A' (xuất hiện ở vị trí 0, 3, 4, 7)
   - Xóa 'A' đầu tiên (vị trí 0): `DBAACDA̲BC`

2. **Lệnh 1** (xóa ký tự lớn nhất đầu tiên):
   - Ký tự lớn nhất: 'D' (xuất hiện ở vị trí 0, 5)
   - Xóa 'D' đầu tiên (vị trí 0): `BAACDABC`

3. **Lệnh 1** (xóa ký tự lớn nhất đầu tiên):
   - Ký tự lớn nhất: 'D' (xuất hiện ở vị trí 4)
   - Xóa 'D' đầu tiên (vị trí 4): `BAACABC`

4. **Lệnh 0** (xóa ký tự nhỏ nhất đầu tiên):
   - Ký tự nhỏ nhất: 'A' (xuất hiện ở vị trí 1, 2, 4)
   - Xóa 'A' đầu tiên (vị trí 1): `BACABC`

**Kết quả:** `BACABC`

---

✅ Đã AC: 2 / 4 submissions