Elearning CodePath – CTP Online Judge

Tổng Trọng số Khoảng

202-TNGTR

🟢 Hard #General

### 📌 Thông tin chung

---

### 📝 Bài toán

**Định nghĩa Trọng số Khoảng:** Trọng số của một dãy số nguyên (subarray) được định nghĩa là **độ chênh lệch** giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy đó.

Giả sử $A[i..j]$ là một dãy con liên tiếp của dãy $A$.
$(A[i..j]) = max(A[i..j]) - min(A[i..j])$

**Yêu cầu:** Cho dãy số nguyên $A$ gồm $N$ phần tử. Hãy tính **tổng trọng số** của **tất cả** các dãy con liên tiếp (subarray) của $A$.

Tổng trọng số cần tìm $S$ là:
$$
S = \sum_{1 \le i \le j \le N} \text{Weight}(A[i..j])
$$

---

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

Dữ liệu vào từ file văn bản `WEIGHT.INP` gồm:

* **Dòng 1:** Chứa số nguyên dương $N$.
* **Dòng 2:** Chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$. Các số được ghi cách nhau ít nhất một dấu cách.

**Giới hạn (Ràng buộc):**
$$
\begin{array}{l}
1 \le N \le 10^5 \\
1 \le A_i \le 10^9
\end{array}
$$
> Kết quả tổng trọng số có thể lên tới cỡ $O(N^2 \cdot \max(A_i)) \approx 10^{10} \cdot 10^9 = 10^{19}$, cần dùng kiểu dữ liệu **64-bit integer** (`long long` trong C++ hoặc `int` trong Python) để lưu trữ kết quả.

---

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

Ghi ra file văn bản `WEIGHT.OUT` một số nguyên duy nhất là kết quả tổng trọng số cần tìm.

---

### ✨ Ví dụ

| Input (`WEIGHT.INP`) | Output (`WEIGHT.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `3` `1 2 3` | `4` | Dãy con và trọng số: $A[1..1]=\{1\}$: $1-1=0$ $A[2..2]=\{2\}$: $2-2=0$ $A[3..3]=\{3\}$: $3-3=0$ $A[1..2]=\{1, 2\}$: $2-1=1$ $A[2..3]=\{2, 3\}$: $3-2=1$ $A[1..3]=\{1, 2, 3\}$: $3-1=2$ Tổng: $0+0+0+1+1+2 = 4$. |
| `4` `3 1 7 2` | `31` | Tổng trọng số của $\frac{4(4+1)}{2} = 10$ dãy con là 31. |

---

### 💡 Gợi ý thuật toán

$$
S = \sum_{i,j} (\max(A[i..j]) - \min(A[i..j])) = \sum_{i,j} \max(A[i..j]) - \sum_{i,j} \min(A[i..j])
$$

Nhiệm vụ chuyển thành tính tổng đóng góp của mỗi phần tử $A_k$ vào tổng $\max$ và tổng $\min$:

1.  **Tổng MAX:** Với mỗi phần tử $A_k$, tính xem có bao nhiêu dãy con liên tiếp $A[i..j]$ mà $A_k$ là phần tử lớn nhất ($i \le k \le j$ và $A_k \ge \max(A[i..j]))$.
    * Sử dụng **Monotonic Stack (Stack đơn điệu)** để tìm chỉ số $L_{max}[k]$ (cột gần nhất bên trái **lớn hơn hoặc bằng** $A_k$) và $R_{max}[k]$ (cột gần nhất bên phải **lớn hơn** $A_k$).
    * Số dãy con mà $A_k$ là MAX là: $(k - L_{max}[k]) \cdot (R_{max}[k] - k)$.
    * Đóng góp vào tổng MAX: $A_k \cdot (k - L_{max}[k]) \cdot (R_{max}[k] - k)$.

2.  **Tổng MIN:** Thực hiện tương tự, sử dụng Monotonic Stack để tìm chỉ số $L_{min}[k]$ và $R_{min}[k]$ để tính số dãy con mà $A_k$ là MIN.

Cả hai bước có thể được thực hiện trong thời gian **$O(N)$** bằng Monotonic Stack, dẫn đến độ phức tạp tổng thể là **$O(N)$**.

✅ Đã AC: 0 / 0 submissions