DIFF
View as PDFHôm nay là buổi học lập trình thi đấu đầu tiên của Aoi. Bài tập đầu tiên của Aoi là in ra một dãy số chỉ toàn các số giống nhau. Tuy nhiên, vì chưa thành thục, dãy số Aoi in ra không giống với yêu cầu của đề. Vì thế, cô bé muốn kiểm tra thử dãy số của mình khác biệt bao nhiêu so với một dãy số chỉ gồm các số giống nhau. Aoi gọi độ khác biệt của một dãy số a là số lượng cặp vị trí ~i~, ~j~ sao cho ~i < j~ và ~a[i] ≠ a[j]~. Sau một hồi suy nghĩ, cô đã đếm được độ khác biệt của dãy số mình in ra (đương nhiên là tính bằng tay). Thế rồi Aoi lại suy nghĩ. Một dãy số sẽ gồm nhiều đoạn liên tiếp, vậy tổng độ khác biệt của tất cả các đoạn con liên tiếp khác rỗng của một dãy số là bao nhiêu? Bài toán này là quá khó với Aoi, vì dù sao đây chỉ mới là buổi học đầu tiên của em ấy. Vì vậy, hãy giúp Aoi nhé.
INPUT
- Dòng đầu tiên là số nguyên dương ~T~ (~T ≤ 10~) là số lượng bộ test
- Dòng đầu tiên của mỗi bộ test gồm số nguyên dương ~n~, là số lượng phần tử của dãy số
- Dòng thứ hai của mỗi bộ test gồm ~n~ số nguyên dương ~a_1, a_2, ... , a_n~ (~a_i ≤ n~)
OUTPUT
- Gồm ~T~ dòng, mỗi dòng là số nguyên duy nhất, là tổng độ khác biệt của tất cả các đoạn con liên tiếp khác rỗng của dãy số của bộ test tương ứng
Ví dụ
Input 1:
3
4
1 1 2 1
4
1 2 3 4
4
1 1 1 1
Output 1:
9
15
0
Subtask 1: 25% số test thỏa ~n ≤ 10~
Subtask 2: 25% số test thỏa ~n ≤ 100~
Subtask 3: 25% số test thỏa ~n ≤ 1000~
Subtask 4: 25% số test thỏa ~n ≤ 100000~
Comments
e Hiếu phá chuỗi AC r
Làm chuỗi mới đi đừng phàn nàn.
:))) HOW?