逆序对

P1908 逆序对

题目

1.jpg

输入输出样例

输入样例#1:
1
2
6
5 4 2 6 3 1
输出样例#1:
1
11

说明

2.jpg

思路

嗯~~

终于用树状数组把这题A了,欧耶

咳咳

题目中对于逆序对说的很清楚:“对于给定的一段正整数序列,逆序对就是序列中ai>aja_i>a_ji<ji<j的有序对”。

这个题,有三种解法:

  1. 暴力枚举每个数字。(肯定不可行,T飞)
  2. 归并排序
  3. 树状数组

今天,我们来谈谈树状数组的解法。

因为,我们都知道,树状数组是维护前缀和的一个数据结构。

那么,很容易想到~~(其实不容易)~~,我们可以用树状数组来维护每一个数之前比它大的数的个数之和。

这就需要排序,从大到小排序。

但是,有可能数会重复,单单按照数进行排序肯定会影响答案的正确性,you know。(好好想一想为什么

所以我们还要改变排序的算法:当数相等时,按照下标从小到大进行排序。

所以compare函数如下:

1
2
3
4
inline bool cmp(int x,int y){
if(a[x].num==a[y].num) return a[x].x>a[y].x;
return a[x].num>a[y].num;
}

code

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
#include<cstdio>
#include<algorithm>

#define int long long
const int maxn=5e5+10;

int n,tree[maxn],r[maxn],ans;

struct type{
int num,x;
}a[maxn];

inline bool cmp(int x,int y){
if(a[x].num==a[y].num) return a[x].x>a[y].x;
return a[x].num>a[y].num;
}

inline int lowbi(int x){return x&(-x);}

inline void update(int x){
while(x<=n){
tree[x]+=1;
x+=lowbi(x);
}
return ;
}

inline int query(int x){
int sum=0;
while(x>=1){
sum+=tree[x];
x-=lowbi(x);
}
return sum;
}

inline int read(){
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}

signed main(){
n=read();
for(register int i=1;i<=n;i++) a[i].num=read(),a[i].x=i,r[i]=i;
std::sort(r+1,r+1+n,cmp);
for(register int i=1;i<=n;i++){
update(r[i]);
ans+=query(r[i]-1);
}
printf("%lld",ans);
return 0;
}
文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/07/09/P1908 逆序对/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论