我是靠谱客的博主 精明嚓茶,这篇文章主要介绍hdu-Frosh Week(树状数组),现在分享给大家,希望可以做个参考。

求逆序数  ----》 离散化

复制代码
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
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; #define M 1000005 typedef __int64 LL; LL a[M]; int n; struct node { LL x,y; }s[M]; bool cmp(node p,node q) { return p.x < q.x; } LL lowbit(LL x) { return x&(-x); } void add(LL pos,LL num) { while(pos <= n) { a[pos]+=num; pos += lowbit(pos); } } LL getsum(LL pos) { LL res = 0; while(pos > 0) { res += a[pos]; pos -= lowbit(pos); } return res; } int main() { while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); for(LL i = 1;i <= n;i++) { scanf("%I64d",&s[i].x); s[i].y = i; } sort(s+1,s+n+1,cmp); LL ret = 0; for(LL i = 1;i <= n;i++) { add(s[i].y,1); ret += i - getsum(s[i].y); } printf("%I64dn",ret); } }


最后

以上就是精明嚓茶最近收集整理的关于hdu-Frosh Week(树状数组)的全部内容,更多相关hdu-Frosh内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(85)

评论列表共有 0 条评论

立即
投稿
返回
顶部