UVa 1428 - Ping pong
传送门
题意
一条大街上住着N个人，每个人有不同的技能值，每场比赛要3个人，其中裁判要住在两个人中间，技能值也要在两人之间，求有多少种比赛方案。
思路
枚举裁判，统计出裁判左边比裁判技能值小的，技能值大的，右边。。。。。然后乘起来相加。
参考了别人的代码，熟悉了一下树状数组。
代码
#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
using namespace std;
const int MAXN = 2e4 + 5;
const int NMAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int a[MAXN], L[MAXN], R[MAXN], x[NMAXN], nmax;
int Sum(int num)
{
int ret = 0;
while (num > 0)
{
ret += x[num];
num -= lowbit(num);
}
return ret;
}
void Add(int num)
{
while (num <= nmax)
{
x[num]++;
num += lowbit(num);
}
}
int main()
{
//freopen("input.txt", "r", stdin);
int n, i, j, T;
scanf("%d", &T);
while (T--)
{
while (~scanf("%d", &n))
{
nmax = -1;
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
nmax = max(nmax, a[i]);
}
memset(x, 0, sizeof x);
for (i = 1; i <= n; i++)
{
Add(a[i]);
L[i] = Sum(a[i] - 1);
}
memset(x, 0, sizeof x);
for (i = n; i >= 1; i--)
{
Add(a[i]);
R[i] = Sum(a[i] - 1);
}
LL ans = 0;
for (i = 1; i <= n; i++)
ans += L[i] * (n - i - R[i]) + (i - L[i] - 1) * R[i];
printf("%lld\n", ans);
}
}
return 0;
}