樹狀數組求逆序對應用：藍橋杯「小朋友排隊」最小不高興程度

樹狀數組求逆序對應用：藍橋杯「小朋友排隊」最小不高興程度

題目轉化

n 個小朋友按身高排序，只能交換相鄰位置。每個小朋友第 k 次交換不高興度增加 k。求總不高興度最小值。
關鍵洞察：每個小朋友交換次數 = 左側比他高的人數 + 右側比他矮的人數 = 以該元素為中心的逆序對總數。
若某元素參與 c 個逆序對，其不高興度 = 1+2+...+c = c(c+1)/2。
總答案 = Σ c_i(c_i+1)/2。

樹狀數組（BIT）計算每個元素的逆序對貢獻

離散化身高值（或直接用值域 1~1e6）。
兩遍掃描：

1. 左→右：BIT.query(a[i]) 得到左側 ≤ a[i] 的個數，左側逆序對 = i - query(a[i])。
2. 右→左：BIT.query(a[i]-1) 得到右側 < a[i] 的個數，即右側逆序對。

c_i = 左側逆序對 + 右側逆序對。

完整代碼 (C++)

#include 
using namespace std;
const int MAXV = 1000010;
int c[MAXV];
long long c_i[100010], tri[100010]; // tri[k] = k*(k+1)/2

int lowbit(int x) { return x & -x; }
void add(int idx, int val) { for (; idx < MAXV; idx += lowbit(idx)) c[idx] += val; }
int sum(int idx) { int s = 0; for (; idx; idx -= lowbit(idx)) s += c[idx]; return s; }

int main() {
    // 預計算三角數
    tri[0] = 0;
    for (int i = 1; i <= 100000; i++) tri[i] = tri[i-1] + i;

    int n;
    while (scanf("%d", &n) != EOF) {
        vector a(n);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        // 離散化（可選，值域 1e6 直接用也可）
        // 這裡直接用值域，注意 a[i] 可能為 0，BIT 下標從 1 開始 → +1
        memset(c, 0, sizeof(c));
        memset(c_i, 0, sizeof(c_i));

        // 左側逆序對：掃描順序，查詢已插入中 > a[i] 的個數
        for (int i = 0; i < n; i++) {
            int x = a[i] + 1;
            int leq = sum(x);          // 左側 ≤ a[i]
            c_i[i] += i - leq;         // 左側 > a[i]
            add(x, 1);
        }

        // 右側逆序對：掃描逆序，查詢已插入中 < a[i] 的個數
        memset(c, 0, sizeof(c));
        for (int i = n-1; i >= 0; i--) {
            int x = a[i] + 1;
            int less = sum(x-1);       // 右側 < a[i]
            c_i[i] += less;
            add(x, 1);
        }

        long long ans = 0;
        for (int i = 0; i < n; i++) ans += tri[c_i[i]];
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度分析

• 離散化（可選）：O(n log n)
• 兩遍 BIT：O(n log V)，V=1e6，log V ≈ 20。
• 空間：O(V + n)。

樣例驗證

輸入：
3
3 2 1
處理：
a=[3,2,1]
i=0: 左側0, 右側<3有2個(2,1) → c=2 → tri=3
i=1: 左側>2有1個(3), 右側<2有1個(1) → c=2 → tri=3
i=2: 左側>1有2個(3,2), 右側0 → c=2 → tri=3
總和 = 9  ✓

避坑指南

1. 身高可能為 0 → BIT 下標 +1 避開 0。
2. c_i 可能達 n，三角數預計算到 n 即可（long long 存儲）。
3. 多組測試用 while(~scanf(...))，每輪 memset 清零 BIT。