Elearning CodePath – CTP Online Judge

Xử lý Xâu Nhị Phân và Truy Vấn

HASH001

🟢 Easy #Hash #Segment Tree #Balanced BST #Data Structure

### 📌 Thông tin chung

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

Cho một xâu nhị phân $S$ ban đầu. Ta cần xử lý 2 loại truy vấn có dạng như sau:

1.  **Xóa (Type 1):** Xóa ký tự ở vị trí $P$. Vị trí các ký tự trong xâu được đánh dấu lại.
2.  **Truy vấn (Type 0):** Từ một đoạn con $[L, R]$ của xâu hiện tại, ta cần in ra số ở hệ thập phân được biểu diễn từ đoạn con trên. Vì kết quả có thể rất to nên ta chỉ cần in kết quả lấy dư cho $1007050321$.

Công thức tính giá trị thập phân $V$ của đoạn con nhị phân $S[L..R]$:
$V = \sum_{i=L}^{R} S[i] \times 2^{(R - i)} \pmod{1007050321}$

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

* Dòng đầu tiên là một xâu nhị phân $S$.
* Dòng tiếp theo gồm số nguyên $Q$ là số lượng truy vấn.
* $Q$ dòng tiếp theo, mỗi dòng là một trong 2 loại truy vấn:
    * **Type 1:** Gồm `1 P` (xóa ký tự ở vị trí $P$).
    * **Type 0:** Gồm `0 L R` (truy vấn đoạn $[L, R]$).

Giới hạn:
* $|S| \le 10^5$.
* $Q \le 10^5$.
* Các số $P, L, R$ trong mỗi test đảm bảo không vượt quá độ dài sâu hiện tại.

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

Với mỗi thao tác loại 0, in ra đáp án cần tìm ($\pmod{1007050321}$).

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `00111` `3` `0 1 5` `1 3` `0 3 4` | `7` `3` |

Giải thích ví dụ:
1.  **Ban đầu:** $S = 00111$.
2.  **Truy vấn `0 1 5`:** $S[1..5] = 00111$.
    * Giá trị thập phân: $0\cdot 2^4 + 0\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 4 + 2 + 1 = 7$. Output: **7**.
3.  **Truy vấn `1 3`:** Xóa ký tự tại vị trí 3 (là '1').
    * $S$ mới: $00\mathbf{1}11 \to 0011$. Độ dài mới là 4.
4.  **Truy vấn `0 3 4`:** $S[3..4] = 11$.
    * Giá trị thập phân: $1\cdot 2^1 + 1\cdot 2^0 = 2 + 1 = 3$. Output: **3**.

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| $1$ | $abs(S), Q \le 1000$ | $30\%$ |
| $2$ | $abs(S), Q \le 5 \times 10^4$ | $30\%$ |
| $3$ | $abs(S), Q \le 10^5$ | $40\%$ |

---

✅ Đã AC: 0 / 0 submissions