学步园

简单的树状数组

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#define MAXN 100010
using namespace std;
int N = MAXN, C[100010], a[20010], _c[20010], _d[20010];
int lowbit(int x)
{
	return x & (-x);
}
int sum(int x)
{
	int ret = 0;
	while (x > 0)
	{
		ret += C[x];
		x -= lowbit(x);
	}
	return ret;
}
void add(int x, int d)
{
	while (x <= N)
	{
		C[x] += d;
		x += lowbit(x);
	}
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t --)
	{
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; ++ i)
		{
			scanf("%d", &a[i]);
		}
		memset(C, 0, sizeof(C));
		for (int i = 0; i < n; ++ i)
		{
			add(a[i], 1);
			_c[i] = sum(a[i]) - 1;
		}
		memset(C, 0, sizeof(C));
		for (int i = n - 1; i >= 0; -- i)
		{
			add(a[i], 1);
			_d[i] = sum(a[i]) - 1;
		}
		long long res = 0;
		//for (int i = 0; i < n; ++ i) printf("%d ", _c[i]); puts("");
		//for (int i = 0; i < n; ++ i) printf("%d ", _d[i]); puts("");
		for (int i = 0; i < n; ++ i)
		{
			res += _c[i] * (n - i - _d[i] - 1) + (i - _c[i]) * _d[i];
		}
		printf("%lld\n", res);
	}
}