Elearning CodePath – CTP Online Judge

Cập nhật Lười trên Mảng

LZARRAY

🟢 Hard #General #Array

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho mảng số nguyên $A = (A_1, A_2, \dots, A_N)$ và $Q$ phép biến đổi.

Mỗi phép biến đổi thứ $k$ được mô tả bằng ba số nguyên $u_k, v_k, d_k$ ($1 \le u_k \le v_k \le N$). Phép biến đổi này có ý nghĩa **tăng giá trị** của tất cả các phần tử $A_i$ có chỉ số nằm trong đoạn $[u_k, v_k]$ lên một lượng là $d_k$.

$\forall i \in [u_k, v_k], \quad A_i \leftarrow A_i + d_k$

Yêu cầu: In ra mảng $A$ sau khi thực hiện **tất cả** $Q$ phép biến đổi nói trên.

---

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

File `LZARRAY.INP` chứa một hoặc nhiều bộ dữ liệu (test cases). Cấu trúc của mỗi bộ dữ liệu:

* **Dòng 1:** Số nguyên dương $N$ – độ dài mảng.
* **Dòng 2:** $N$ số nguyên $A_1, A_2, \dots, A_N$ (các phần tử ban đầu của mảng).
* **Dòng 3:** Số nguyên dương $Q$ – số lượng phép biến đổi.
* **$Q$ dòng tiếp theo:** Mỗi dòng mô tả một phép biến đổi gồm ba số nguyên $u, v, d$.

Dòng cuối cùng của file ghi một số $0$ để báo hiệu kết thúc file dữ liệu.

**Giới hạn (Ràng buộc):**
Giới hạn được áp dụng trên tổng các bộ dữ liệu.
* $1 \le N \le 10^5$
* $1 \le Q \le 10^5$
* $|A_i| \le 10^9$
* $|d| \le 10^9$

**Subtasks:**
* **Subtask 1 (50%):** $N, Q \le 1000$.
* **Subtask 2 (50%):** $N, Q \le 10^5$.

> Do $|A_i|$ và $|d|$ lớn, tổng tích lũy của $A_i$ có thể vượt quá $2^{32}$. Cần dùng kiểu dữ liệu **64-bit integer** (`long long` trong C++/`int` trong Python) để lưu trữ các phần tử của mảng và kết quả cuối cùng.

---

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

Ghi ra file `LZARRAY.OUT`. Với mỗi bộ dữ liệu, in ra một dòng $N$ số nguyên mô tả mảng $A$ sau $Q$ phép biến đổi. Các số cách nhau một khoảng trắng.

---

### ✨ Ví dụ

| Input (`LZARRAY.INP`) | Output (`LZARRAY.OUT`) |
| :--- | :--- |
| `5` `2 1 3 2 5` `4` `1 2 8` `2 5 7` `3 5 -10` `1 5 6` `0` | `16 22 6 5 8` |

---

### 🧪 Giải thích Ví dụ

Mảng $A$ ban đầu: $[2, 1, 3, 2, 5]$

| TT | Truy vấn $(u, v, d)$ | Thay đổi | Mảng $A$ sau thay đổi |
| :--- | :--- | :--- | :--- |
| 1 | $(1, 2, 8)$ | $A[1..2] \leftarrow +8$ | $[10, 9, 3, 2, 5]$ |
| 2 | $(2, 5, 7)$ | $A[2..5] \leftarrow +7$ | $[10, 16, 10, 9, 12]$ |
| 3 | $(3, 5, -10)$ | $A[3..5] \leftarrow -10$ | $[10, 16, 0, -1, 2]$ |
| 4 | $(1, 5, 6)$ | $A[1..5] \leftarrow +6$ | $[16, 22, 6, 5, 8]$ |

Kết quả cuối cùng: $16 \ 22 \ 6 \ 5 \ 8$.

✅ Đã AC: 0 / 0 submissions