Elearning CodePath – CTP Online Judge

Cập Nhật Gán và Truy Vấn Tổng Đoạn

SEG007

🟢 Medium #Segment Tree #Interval #Data Structure

### 📌 Thông tin chung

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

Cho mảng $A$ có độ dài $N$ chỉ gồm các phần tử $0$ hoặc $1$. Ban đầu tất cả các phần tử của mảng đều là $0$. Ta có 3 loại thao tác như sau:

1.  **Gán 1 (Type 1):** `1 l r` - Gán toàn bộ các phần tử trong đoạn $[l, r]$ là $1$.
    $    A[i] \leftarrow 1, \quad \forall i \in [l, r]  $
2.  **Gán 0 (Type 0):** `0 l r` - Gán toàn bộ các phần tử trong đoạn $[l, r]$ là $0$.
    $    A[i] \leftarrow 0, \quad \forall i \in [l, r]    $
3.  **Truy vấn (Type 2):** `2 l r` - Cần hỏi xem trong đoạn $[l, r]$ có bao nhiêu phần tử $i$ thỏa $A[i] = 1$ .
    $    \sum_{i=l}^{r} A[i]$

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

* Dòng đầu tiên là số nguyên $N$ (độ dài mảng) và $Q$ (số thao tác).
* $Q$ dòng tiếp theo, mỗi dòng có dạng 1 trong 3 loại thao tác.

Giới hạn:
* $N, Q \le 10^5$.
* $1 \le l \le r \le N$.

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

Với mỗi thao tác loại 2, in ra đáp án cần tìm (số lượng phần tử bằng 1 trong đoạn $[l, r]$).

---
### ✨ Ví dụ

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

---
### 🏷 Phân tích và Ràng buộc

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- | 
| $1$ | $N, Q \le 1000$ | $30\%$ |
| $2$ | $N, Q \le 10^5$  | $70\%$ |

---

✅ Đã AC: 2 / 4 submissions