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<j\le n\)

Thì để tính \(S_k\), đầu tiên ta sắp xếp lại mảng \(S_k\) theo thứ tự tăng dần. Và ta có nhận xét rằng: Việc sắp xếp lại mảng không làm ảnh hưởng đến giá trị \(F(S_k)\) nhưng chúng sẽ giúp ta dễ dàng tính được \(F(S_k)\) hơn

Khi đó ta sẽ luôn có: \(S_k[i]<S_k[j]\) với mọi \(1\le i<j\le n\). Tức là: \(F(S_k)=\sum (S_k[j]-S_k[i])\) với mọi \(1\le i<j\le n\)

Đến đây, ta chỉ cần nháp bằng tay ra thì ta dễ dàng tìm được công thức của \(F(S_k)\) như sau:

\(F(S_k) = \sum\limits_{t=2}^{n}((t-1)S_k[t] - presum[t-1])\) trong đó \(presum[t]=S_k[1]+S_k[2]+...+S_k[t]\). Để đảm bảo thuật toán chạy trong thời gian thì ta nên tính trước mảng \(presum\)

Như vậy là bài toán đã được giải quyết xong, các bạn có thể tham khảo code tại đây