Inversion Number algorithm Note
転倒数的意義
簡單來說就是泡泡排序的交換次數
但為什麼不直接實做排序再計算次數呢？
泡泡搜尋法的最差複雜度為 O(N^2）而使用Bit計算可以達到 O(NlogN)
分析泡泡排序法的交換次數
1. 如何判斷一個數字會交換的次數？
泡泡搜尋法的交換規則為左邊的值大於右邊的值即發生交換。
2. 計算總交換次數
由此可以得知總交換次數為所有數字之現在位置的左邊大於自己值的個數總和。
相對位置在Ai左邊而值大於Ai之數後簡稱前置大數。
實現計算所有前置大數的原理(與計數排序法counting sort類似)
例題1: Atcoder s001_j
例題2: Atcoder abc264_d
1. BIT內以A的值為index紀錄出現過數字。
| index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| A: |
8 |
3 |
6 |
5 |
2 |
4 |
1 |
9 |
7 |
| BIT: |
|
|
|
|
|
|
|
|
|
| index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| A: |
(8) |
3 |
6 |
5 |
2 |
4 |
1 |
9 |
7 |
| BIT: |
|
|
|
|
|
|
|
1 |
|
| index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| A: |
8 |
(3) |
6 |
5 |
2 |
4 |
1 |
9 |
7 |
| BIT: |
|
|
1 |
|
|
|
|
1 |
|
| index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| A: |
8 |
3 |
(6) |
5 |
2 |
4 |
1 |
9 |
7 |
| BIT: |
|
|
1 |
|
|
1 |
|
1 |
|
| index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| A: |
8 |
3 |
6 |
5 |
(2) |
4 |
1 |
9 |
7 |
| BIT: |
|
|
1 |
|
1 |
1 |
|
1 |
|
| index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| A: |
8 |
3 |
6 |
5 |
2 |
(4) |
1 |
9 |
7 |
| BIT: |
|
1 |
1 |
|
1 |
1 |
|
1 |
|
以此推計算到第六格也就是4的位置得到BIT為011011010，BIT的特性使我們可以快速加總出前綴合，而我們現在要判斷4的前置大數，透過加總BIT中1~4號位可以得出前置小數為2，在用前置數字的數量減去前置小數即可獲得前置大數的數量。關鍵： 做到第幾位就算到第幾位。
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
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using namespace std;
#define io ios_base::sync_with_stdio(0), cin.tie(0);
typedef long long int ll;
int n;
struct BIT{
private:
vector<int> bit;
public:
BIT(void){
bit.resize(n+1);
}
int sumup(int x){
int temp = 0;
for(int i=x;i>0;i-=i&-i){
temp += bit[i];
}
return temp;
}
void update(int y){
for(int i=y;i<=n;i+=i&-i) bit[i]++;
}
};
signed main(){
cin >> n;
vector<int> data(n);
for(int i=0;i<n;i++) cin >> data[i];
BIT b;
ll ans = 0;
for(int i=0;i<n;i++){
ans += i - b.sumup(data[i]);
b.update(data[i]);
}
cout << ans << endl;
return 0;
}
|
參考資料： 転倒数