首页 > 代码库 > UVA 1428 - Ping pong(树状数组)
UVA 1428 - Ping pong(树状数组)
UVA 1428 - Ping pong
题目链接
题意:给定一些人,从左到右,每个人有一个技能值,现在要举办比赛,必须满足位置从左往右3个人,并且技能值从小到大或从大到小,问有几种举办形式
思路:利用树状数组处理出每个位置左边比它小的个数和右边比他小的个数和,那么左边和右边大就也能计算出来,那么比赛场次为左边小*右边大+左边大*右边小。
代码:
#include <cstdio> #include <cstring> const int N = 100005; int t, n, a[N]; long long bit[N], lx[N], rx[N]; inline int lowbit(int x) { return x&(-x); } void add(int x, long long val) { while (x < N) { bit[x] += val; x += lowbit(x); } } long long Query(int x) { long long ans = 0; while (x > 0) { ans += bit[x]; x -= lowbit(x); } return ans; } int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); memset(bit, 0, sizeof(bit)); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); lx[i] = Query(a[i]); add(a[i], 1); } memset(bit, 0, sizeof(bit)); for (int i = n - 1; i >= 0; i--) { rx[i] = Query(a[i]); add(a[i], 1); } long long ans = 0; for (int i = 0; i < n; i++) ans += lx[i] * (n - i - 1 - rx[i]) + (i - lx[i]) * rx[i]; printf("%lld\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。