Bài tập đếm bộ ba nghịch thế của mảng trong O(n log n)

[Karma131 (Wakan_za_rai)]

Cho 1 mảng a độ dài n, nếu i<j<k và a[i]>a[j]>a[k] thì bộ (i,j,k) thoả mãn là 1 bộ ba nghịch thế . Đếm số cặp thoả mãn với O(nlogn)
Giúp em với ạ ;-;-;-;

[rogp10]

Bài này không dễ đâu Bạn làm thử cặp (i, j) trước đã.

[tcm (Người bí ẩn)]

Bạn có thể duyệt từ cuối về, dùng 2 cây fenwick như sau:

• cây fenwick 1 có nhãn a[k] lưu tần số xuất hiện của giá trị này.
• cây fenwick 2 có nhãn a[j] lưu tần số xuất hiện của cặp (aj, ak).

Tư tưởng là bạn dùng cây fenwick 1 để cập nhật cây fenwick 2, và dùng cây fenwick 2 để tính đáp án.

Có thể tổng quát hóa bài toán thành đếm số bộ k-nghịch thế là (i1 < i2 < … < ik) sao cho (a[i1] > a[i2] > … > a[ik]). Khi đó bạn có thể implement 1 cái rừng cây fenwick và làm tương tự với đpt O(knlogn).