P1908逆序对题解

水一篇博客吧。寒假+2020年第一篇博客。既然是第一篇就要水嘛

这道题是很水的一道题。利用树状数组的特性可以很简单的解决。

前置知识:树状数组、离散化

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
#include<bits/stdc++.h>
using namespace std;
int n,m=0;
long long a[500010],b[500010],c[500010],d[500010];
inline int lowbit(int x) {
return x&-x;
}
void discrete() {
for(int i=1;i<=n;i++)
b[i]=a[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
if(i==1 || b[i]!=b[i-1])
d[++m]=b[i];
}
int querydis(long long x) {
return lower_bound(d+1,d+1+m,x)-d;
}
void add(int x) {
for(;x<=n;x+=lowbit(x))
c[x]++;
}
long long query(int x) {
long long ans=0;
for(;x;x-=lowbit(x))
ans+=c[x];
return ans;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
discrete();
long long ans=0;
for(long long i=1;i<=n;i++) {
add(querydis(a[i]));
ans+=i-query(querydis(a[i]));
}
printf("%lld\n",ans);
return 0;
}
支持原创!从我做起~ 支付宝搜“611460069”领到的红包也可以赞助哦~
召唤伊斯特瓦尔