d542: 10810 - Ultra-QuickSort

2021-05-06 23:24:22 +0800 CST Tags: binary-indexed-tree, inversion-pair

出處：https://zerojudge.tw/ShowProblem?problemid=d542
提交：https://zerojudge.tw/Submissions?problemid=d542&account=allllllan123456

問題：請求出至多 500000 個非負整數 (值至多 999999999) 的逆序對數，假設可能會有重複的值。

解法：逆序對數兩個經典解法就是樹狀數組 (binary indexed tree, BIT) 或合併排序法 (mergesort)，這邊想嘗試較精巧輕便的 BIT 方法。我們的手法如下，先把原數列的每個數字重新編號成它在整個數列的排名，舉例來說，[9, 4, 1, 4, 0, 5] 會被重新編寫成 [1, 3, 4, 3, 5, 2]。接著 BIT 陣列維護由小到大每個數字出現次數的加總，那麼我們只要按照原數列的順序把計數器更新到定位，並同時加總已經出現過幾個比當前的數字還要小的數字，就能統計出逆序數對的總數。舉例來說，第一個數字 9 的位置在 1，但它前面都沒有人，所以不影響答案，同時更新加總前的 BIT (令為 BIT$'$) 為 [1, 0, 0, 0, 0]；第二個數字 4 的位置在 3，它前面已經有一個人比它大，答案更新為 1 對，同時更新 BIT$'$ 為 [1, 0, 1, 0, 0]；接著第三個數字 1 的位置在 4，它前面已經有兩個人比它大，答案累計為 3 對，同時更新 BIT$'$ 為 [1, 0, 1, 1, 0]；第四個數字 4 的位置在 3，它前面只有一個人比它大，答案累計為 4 對，同時更新 BIT$'$ 為 [1, 0, 2, 1, 0]；第五個數字 0 的位置在 5，它前面共有四個人比它大，答案累計為 8 對，同時更新 BIT$'$ 為 [1, 0, 2, 1, 1]；最後一個數字 5 的位置在 2，它前面只有一個數字比它大，答案累計為 9 對，同時更新 BIT$'$ 為 [1, 1, 2, 1, 1]。

實作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include <bits/stdc++.h>
using namespace std;

inline int lowbit(int i) { return i & -i; }

int arr[500000];

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int n, id[500000], bit[500000];
    while (cin >> n && n) { memset(bit, 0, sizeof bit);
        for (int i=0; i<n; i++) { id[i] = i; cin >> arr[i]; }
        sort(id, id+n, [](int a, int b) { return arr[a] > arr[b]; });
        int id2 = 1; // note the index starts from 1
        for (int i=0; i<n; i++) {
            int old = arr[id[i]];
            arr[id[i]] = id2;
            if (i+1<n && old>arr[id[i+1]]) id2++;
        }
        long long ans = 0; // id2 := number of distinct elements in arr
        for (int i=0; i<n; i++) {
            for (int j=arr[i]-1; j; j-=lowbit(j))
                ans += bit[j];
            for (int j=arr[i]; j<=id2; j+=lowbit(j))
                bit[j]++;
        }
        cout << ans << '\n';
    }
    return 0;
}

結果： Example image