首页 > 代码库 > ACM-ICPC LA 4329 Ping pong（树状数组）
ACM-ICPC LA 4329 Ping pong（树状数组）
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2330
参考资料：《算法入门经典训练指南》刘汝佳 P197
这本书上面写的题目大意、解题思路都写出来了。
在这我贴上自己的
AC代码：
1 #include<stdio.h> 2 #include<string.h> 3 4 #define PEOPLE 20001 5 #define VALUE 100001 6 7 typedef long long LL; 8 9 int n, a[PEOPLE], amin[PEOPLE], amax[PEOPLE], tree[VALUE];10 11 12 int lowbit(int x){13 return x & -x;14 }15 16 void add(int x, int d){17 while(x < VALUE){18 tree[x] += d;19 x += lowbit(x);20 }21 }22 23 int sum(int x){24 int ret = 0;25 while(x > 0){26 ret += tree[x];27 x -= lowbit(x);28 }29 return ret;30 }31 32 int main(){33 int t;34 scanf("%d", &t);35 while(t--){36 scanf("%d", &n);37 for(int i = 1; i <= n; ++i){38 scanf("%d", &a[i]);39 }40 41 memset(tree, 0, sizeof(tree));42 for(int i = 1; i <= n; ++i){43 amin[i] = sum(a[i] - 1);//第i个人 统计在第i个人的左边并且技能值小于 的总人数44 amax[i] = i - 1 - amin[i];//统计 技能值大于第i个人并且在左边的总人数45 add(a[i], 1);46 }47 48 LL ans = 0;49 memset(tree, 0, sizeof(tree));50 for(int i = n; i >= 1; --i){51 LL bmin = sum(a[i] - 1);//统计 技能值小于第i个人并且在第i个人的右边的总人数52 ans += bmin * amax[i] + (n - i - bmin) * amin[i];53 add(a[i], 1);54 }55 printf("%lld\n", ans);56 }57 return 0;58 }
ACM-ICPC LA 4329 Ping pong（树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。