HDOJ2838(트리 배열)

모든 역서수의 합을 구하다
분석: 수 a에 대해 그의 역계수 대조의 합은 역계수 *a+a 이전에 a보다 큰 수이다.두 개의 나무 상수 그룹을 열고, 하나는 역순 대수를 구하고, 하나는 화합을 구한다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100001
using namespace std;
struct tree
{
	int t;
	long long sum;
}tree[MAXN];
int n;
int lowbit(int i)
{
	return i&(-i);
}
void update(int i, int s, int x)
{
	while (i <= n)
	{
		tree[i].t += x;
		tree[i].sum += s;
		i = i + lowbit(i);
	}
}
int queryx(int n)
{
	int ans = 0;
	while (n > 0)
	{
		ans += tree[n].t;
		n -= lowbit(n);
	}
	return ans;
}
long long  querysum(int n)
{
	long long ans = 0;
	while (n > 0)
	{
		ans += tree[n].sum;
		n -= lowbit(n);
	}
	return ans;
}
int main()
{
	while (~scanf("%d", &n))
	{
		long long ans = 0;
		memset(tree, 0, sizeof(tree));
		for (int i = 1; i <= n; i++)
		{
			int a;
			scanf("%d", &a);
			update(a, a, 1);
			long long k = i - queryx(a);
			if (k != 0)
			{
				long long k1 = querysum(n) - querysum(a);// n       a     ，  a     。
				ans += k*a + k1;
			}
		}
		printf("%lld
", ans);
	}
	return 0;
}