题目链接
题目概述
给一组正整数，采用冒泡排序，求排序过程中交换的次数。
题目分析
题目表述得很玄乎，但其实这就是求逆序的数量。
树状数组
树状数组是一种用于高效处理对一个存储数字的列表进行更新及求前缀和的数据结构，可以以 $O(\log n)$ 的效率来执行更新和求和。
下面是板子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #define lowbit(x) x&-(x)
#define MAXN 50005
int tree[MAXN];
void add(int x, int delta){
for(int i=x; i<=MAXN; i+=lowbit(x))
tree[i]+=delta;
}
int sum(int x){
int sum;
for(int i=x; i>0; i-=lowbit(x))
sum+=tree[i];
return sum;
}
|
需要注意的是，树状数组要求下标从1开始。
离散化
由于题目的输入范围太大，直接开数组肯定会爆内存，需要将输入的数离散化（可以理解为给每个数一个独一无二的id，并且这个id的范围不会太大），根据id的范围来开数组，就不会爆内存。至于排序，我们也可以对id来间接排序。
完整代码
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
42
43
44
45
46
47
48
49
50
51
52
| #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define LL __int64
using namespace std;
int tree[500050],nums[500050],id[500050],N = 500050;
int cmp(const int x,const int y){
return nums[x] < nums[y];
}
#define lowbit(x) x&-(x)
void add(int i,int x){
while(i <= N){
tree[i] += x;
i += lowbit(i);
}
}
LL sum(int n){
LL sum = 0;
while(n > 0){
sum += tree[n];
n -= lowbit(n);
}
return sum;
}
int main(){
int N;
while(cin >> N && N){
for(int i = 1; i <= N; ++i){
cin >> nums[i];
id[i] = i;
}
sort(id+1,id+N+1,cmp);
LL ans = 0;
for(int i = 1; i <= N; ++i) {
add(id[i],1);
ans += i - sum(id[i]);
}
cout << ans << endl;
}
return 0;
}
|
自我总结
之前一直在想，用前缀和来求区间和不是也很快，为什么还要用树状数组，后来明白，往往是需要频繁地“更新”操作，树状数组在更新的时候复杂度是 $O(\log n)$ ，比前缀和快。
一开始不明白为什么会要用到id数组，看题解后明白，因为输入范围比较大，不好直接开数组记录每个数出现与否，所以要将输入的数与一个id对应，这样可以通过对id进行排序，从而间接得到排序后的数组。
树状数组要求输入为正数，如果输入的数中有小于等于0的情况，要转换为正数。