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;
}

这篇关于UVA 1428 - Ping pong(树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---