Đầu tiên, chúng ta cần dựng hai dãy \(D\) và \(E\). Việc dựng hai dãy này khá đơn giản, chỉ việc sort lại dãy ban đầu. Các bạn có thể lưu một vector chứa các pair<int, int> (giá trị, vị trí) rồi sort lại.

Bài toán quy về: Tính tổng \(|D_i - D_j| * min(E_i, E_j)\) với mọi cặp \(i < j\).

Đến đây, chúng ta có 3 hướng tiếp cận:

Hướng 1: For theo j rồi tính tổng trên với mọi \(i < j\). Tuy nhiên cách này không khả thi vì rất khó xử lý trị tuyệt đối và min.

Hướng 2: For theo thứ tự tăng dần của \(D_i\). Nói cách khác, chúng ta sắp xếp lại thứ tự các bộ \((D_i, E_i)\) sao cho \(D_i\) tăng dần.

Lúc này, chúng ta có thể for theo j và biết được các số \(i < j\) thì \(|D_i - D_j| = D_j - D_i\). Như vậy tổng cần tính là \((D_j - D_i) * min(E_i, E_j)\). Các bạn có thể xử lý tiếp, nhưng phần còn lại là khá khó.

Hướng 3: For theo thứ tự tăng dần của \(E_i\). Nói cách khác, chúng ta sắp xếp lại thứ tự các bộ \((D_i, E_i)\) sao cho \(E_i\) tăng dần.

Lúc này, với \(i < j\) thì \(min(E_i, E_j) = E_i\). Như vậy, lúc for j, ta cần tính tổng sau với mọi \(i < j\): \(|D_j - D_i| * E_i\).

Tuy nhiên, bài toán vẫn phức tạp vì dính \(E_i\). Thay vào đó, chúng ta có thể for i và tính tổng sao với mọi \(j > i\): \(|D_j - D_i| * E_i\). Tổng này chính là:

Để tính toán tổng trong ngoặc, chúng ta cần lưu 2 dữ kiện:

• Có bao nhiêu số nhỏ hơn \(D_i\) trong các số \(D_{i+1}, ..., D_n\)?
• Tổng các số đó là bao nhiêu?

Đây chính là ứng dụng của BIT. Chúng ta có thể for ngược i từ n về 1 và lưu hai cây BIT cho hai dữ kiện trên.