逆序对

对于逆序对,是这样定义的:对于给定的一段正整数序列,逆序对就是序列中$a_i>a_j$且$i<j$的有序对。

求逆序对一般两种方法,一种是归并排序,另一种是离散化+树状数组。

这里说树状数组的做法。

先考虑暴力做法,类似桶排序的思想,每得到一个值就放入桶中,然后统计所有大于这个数的数量。

对此做法优化:离散化,存一个数组表示当前数是所有数的第几大。

基于此做法继续优化,我们发现统计过程中需要不断的求和和修改,于是引入树状数组来维护。

洛谷P1908逆序对

注意这个题,其实一开始数据很水,随便离散化一下就谁过去了。

但是,后来加强数据了!

所以,

离散化一定要去重!

离散化一定要去重!

离散化一定要去重!

代码(C++11):

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using std::cerr;
using std::endl;

using LL=long long;

#define lowbit(x) x&(-x)

class BinaryIndexed
{
private:
int n;
int *tree;

public:
BinaryIndexed(int n):n(n)
{
tree=new int[n+1];
memset(tree,0,(n+1)*sizeof(int));
}
~BinaryIndexed()
{
delete [] tree;
}

void Add(int x,int num)
{
while(x<=n)
{
tree[x]+=num;
x+=lowbit(x);
}
}

LL Sum(int x)
{
LL ans=0;
while(x>0)
{
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
};

std::vector<int> number,rank;

int main()
{
int n;
scanf("%d",&n);
static BinaryIndexed *Tree=new BinaryIndexed(n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
number.push_back(x);
rank.push_back(x);
}
std::sort(number.begin(),number.end());//排序
auto End=std::unique(number.begin(),number.end());//去重
for(auto &it : rank)
it=std::lower_bound(number.begin(),End,it)-number.begin()+1;//查询排名
LL ans=0;
for(auto it : rank)
{
Tree->Add(it,1);
ans+=Tree->Sum(n)-Tree->Sum(it);
}
printf("%lld\n",ans);
number.clear();
rank.clear();
delete Tree;
return 0;
}