Elearning CodePath – CTP Online Judge

TREES

SEG001

🟢 Hard #General #Segment Tree #Interval #Data Structure

### 📌 Thông tin chung

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

Doraemon là một nhân vật hư cấu trong loạt Manga nổi tiếng được sáng tác bởi Fujiko F. Fujio. Doraemon là một chú mèo máy đến từ tương lai (thế kỷ 22), được gửi về quá khứ để giúp đỡ một cậu bé tên là Nobita Nobi. Doraemon có một túi thần kỳ gọi là "4D Pocket" từ đó cậu có thể rút ra rất nhiều bảo bối và công cụ hiện đại để giúp Nobita giải quyết các vấn đề trong cuộc sống hàng ngày. Một hôm, Nobita được mẹ giao cho nhiệm vụ trồng cây để tăng mỹ quan cho ngôi nhà. Nobita đã tìm đến Doraemon nhờ giúp. Trước sự cầu cứu tha thiết của Nobita, Doraemon đã rút trong túi thần kỳ mượn một bảo bối trồng cây. Ban đầu, các cây có chiều cao là 0 và được xếp thành 1 hàng thẳng được đánh số từ 1 đến $n$, bảo bối của Doraemon có 2 chức năng là tăng chiều cao tất cả các cây trong đoạn $[L, R]$ lên $W$ hoặc khiến chiều cao các cây trong đoạn $[L, R]$ trở thành chiều cao hiện tại của nó nhân với $W$. Ngoài ra, Nobita cũng muốn biết việc trồng cây trong một đoạn $[L, R]$ nào đó của mình có hiệu quả hay không. Độ hiểu quả của việc trồng cây lại liên quan tới tổng chiều cao của các cây trong đoạn đó. Nobita cần biết được thông số này nhưng lúc này Doraemon đang đi mua bánh rán vì vậy bạn là người được Nobita tin tưởng để tính giúp cậu ấy trong quá trình trồng cây.

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

* Dòng đầu tiên gồm hai số nguyên dương $N$ và $Q$ ($N, Q \le 10^5$) với $Q$ là số thao tác của Nobita.
* $Q$ dòng tiếp theo nhập vào như sau:
    * Đầu tiên nhập vào $Type$, là loại thao tác của Nobita.
    * **Nếu Type = 1:** Thì nhập vào 3 số nguyên $L, R, W$ ($1 \le L \le R \le N, 1 \le W \le 10^9$), tức là tăng đoạn chiều cao các cây trong đoạn $[L, R]$ lên một lượng $W$.
    * **Nếu Type = 2:** Thì nhập vào 3 số nguyên $L, R, W$ ($1 \le L \le R \le N, 1 \le W \le 10^9$), tức là biến chiều cao các cây trong đoạn $[L, R]$ thành chiều cao hiện tại của nó nhân với $W$.
    * **Nếu Type = 3:** Thì nhập vào 2 số nguyên $L, R$ ($1 \le L \le R \le N$), tức là Nobita đang hỏi bạn về tổng chiều cao các cây trong đoạn $[L, R]$.

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

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

Câu trả lời cho các truy vấn loại 3, do kết quả có thể rất lớn nên in ra kết quả chia dư cho $10^9 + 7$.

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `5 5` `1 2 3 2` `1 1 5 1` `3 1 4` `2 1 3 2` `3 1 4` | `8` `15` |

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Phép toán | Độ phức tạp yêu cầu | Tỷ lệ điểm |
| :--- | :--- | :--- | :--- | :--- |
| 1 | $N, Q \le 1000$ | Chỉ có Type 1 và 3 | $O(N \cdot Q)$ hoặc $O(Q \log N)$ | $30\%$ |
| 2 | $N, Q \le 10^5$ | Chỉ có Type 1 và 3 | $O(Q \log N)$ | $30\%$ |
| 3 | $N, Q \le 10^5$ | Cả ba Type 1, 2, 3 | $O(Q \log N)$ | $40\%$ |

---

✅ Đã AC: 5 / 16 submissions