Elearning CodePath – CTP Online Judge

Giá trị Dãy con

VALSEQ

🟢 Easy #Segment Tree

### 📌 Thông tin chung

| Mục | Chi tiết | 
| :--- | :--- | :--- |
| **Tên File Input** | `VALSEQ.INP` | 
| **Tên File Output** | `VALSEQ.OUT` |

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

Cho một dãy số không âm $A = (A_1, A_2, \dots, A_N)$.

**Giá trị** của một dãy số được định nghĩa là **hiệu của phần tử lớn nhất và phần tử nhỏ nhất** trong dãy số đó.
$$
\text{Value}(A) = \max(A) - \min(A)
$$

Yêu cầu: Tính tổng của giá trị của **tất cả các dãy con gồm các phần tử liên tiếp** của dãy số đã cho.

$$
\text{Total Value} = \sum_{1 \le i \le j \le N} \text{Value}(A[i \dots j]) = \sum_{1 \le i \le j \le N} (\max(A[i \dots j]) - \min(A[i \dots j]))
$$

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

Dữ liệu vào từ file `VALSEQ.INP`:

* Dòng đầu: Ghi số nguyên dương $N$ là số phần tử của dãy số.
* $N$ dòng tiếp theo: Mỗi dòng ghi một số tự nhiên lần lượt thể hiện các phần tử của dãy đã cho.

Giới hạn:
* $2 \le N \le 300000$.
* $0 \le A_i \le 10^6$.

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

Ghi ra file `VALSEQ.OUT` một số nguyên duy nhất là tổng giá trị của tất cả các dãy con gồm các phần tử liên tiếp của dãy đã cho.

---
### ✨ Ví dụ

| Input (`VALSEQ.INP`) | Output (`VALSEQ.OUT`) | |
| :--- | :--- | :--- |
| `4` `3` `1` `7` `2` | `31` | |

| Input (`VALSEQ.INP`) | Output (`VALSEQ.OUT`) | |
| :--- | :--- | :--- |
| `4` `7` `5` `7` `5` | `12` | |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $40\%$ |
| 2 | $N \le 300000$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions