Elearning CodePath – CTP Online Judge

Tổng Trọng Số Đoạn Con

TS_TOTAL_SUBSEGMENT_

🟢 Easy #General #Hash

### 📌 Thông tin chung

### 📝 Bài toán

Cho một dãy $N$ số nguyên $A = (A_1, A_2, \dots, A_N)$.

**Trọng số** của một đoạn con liên tiếp $A[l..r]$ ($1 \le l \le r \le N$), ký hiệu là $W(l, r)$, được định nghĩa là **số lượng các cặp chỉ số** $(i, j)$ nằm trong đoạn $[l, r]$ thỏa mãn điều kiện $i < j$ và $A_i = A_j$.

$$
W(l, r) = \left| \left\{ (i, j) \mid l \le i < j \le r \text{ và } A_i = A_j \right\} \right|
$$

Yêu cầu: Tính **tổng trọng số** của **tất cả** các đoạn con liên tiếp của dãy $A$.
$Tổng trọng số = \sum_{1 \le l \le r \le N} W(l, r)$

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

* Dòng 1: Số nguyên dương $T$ ($1 \le T \le 10^5$) – số lượng truy vấn.
* $T$ khối dòng tiếp theo: Mỗi khối mô tả một bộ test:
    * Dòng 1: Số nguyên dương $N$ ($1 \le N \le 10^5$) – số lượng phần tử.
    * Dòng 2: $N$ số nguyên dương $A_1, A_2, \dots, A_N$ – các phần tử của dãy ($1 \le A_i \le 10^9$).

Giới hạn: Tổng của tất cả $N$ trong các truy vấn không vượt quá $10^5$.

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

Với mỗi truy vấn, in ra một số nguyên duy nhất là tổng trọng số của tất cả các đoạn con.

---

✅ Đã AC: 0 / 0 submissions