#54649: 解題思路
uf018127
(Jacob)
這題轉了幾個彎，若1≤i≤j，題目問有多少數對(i, j)讓ai到aj的平均值≥lo且≤hi，要轉成
1. 計算有多少數對(i, j)讓ai到aj的平均值≥lo
2. 計算有多少數對(i, j)讓ai到aj的平均值>hi
3. 然後前者減後者
步驟1跟2解法一樣，以步驟1為例，令數列xi = ai - lo，題目變成
- 若1≤i≤j，計算有多少數對(i, j)讓xi到xj的和≥0
把x轉成前綴和Pi=x1到xi的和，題目變成
- 若0≤i<j，計算有多少數對(i, j)讓Pj-Pi≥0，再轉成
- 若0≤i<j，計算有多少數對(i, j)讓Pj≥Pi
這時題目變成計算「逆序數對」數量，可以在MergeSort的過程中順便算出來，步驟1跟步驟2共用一個MergeSort
- 步驟1的MergeSort逆序函數為Pi ≤ Pj
- 步驟2的MergeSort逆序函數為Pi < Pj
如何用MergeSort計算逆序數對請Google「逆序數對」