Mình xin chia sẻ lời giải bài này như sau:

Trước tiên, ta phải phân hoạch mảng \(a\) đã cho thành các tập hợp con, trong đó những vị trí nào mà có cùng giá trị thì sẽ thuộc về một tập. (Ta chú ý rằng: các tập hợp con ở đây chỉ chứa vị trí của các phần tử mà có giá trị giống nhau)

Chẳng hạn ở ví dụ \(2\) của đề bài, ta sẽ phân hoạch \((1,2,1,2)\) thành \(2\) tập hợp con, giả sử đó là hai tập \(A=(1,3)\) và \(B=(2,4)\). Vì những vị trí trong tập hợp \(A\) đều có cùng giá trị là \(1\) và những vị trí trong tập hợp \(B\) đều chứa giá trị là \(2\).

Để thực hiện bước phân hoạch này, ta sử dụng \(map<int,vector<int>>\) (Các bạn có thể hiểu rõ hơn ở phần code).

Sau khi đã phân hoạch xong, bước tiếp theo sẽ là tính toán.

Giả sử: Mảng \(a\) của ta được phần thành \(q\) tập hợp con \(S_1,S_2,...,S_q\). Khi đó công thức \(A=\sum\ |i-j| = \sum \limits_{k=1}^{q} F(S_k)\).

Trong đó \(F(S_k)=\sum |S_k[i]-S_k[j]|\) với mọi $1\le i