题目链接

题意：

有n个人要进行乒乓球比赛，每一个人都一个能力值。每一个人出现的次序就是他们住的位置

如今要求进行一场比赛，三个人，裁判的能力值在两个选手之间，住的位置也在两个人的之间

问这样的比赛一共能够进行多少次

思路：

用树状数组做，否则TLE，先从左到右扫一遍，计算每点左边大的个数和小的个数，

再从右到左扫一遍，计算每点右边大和小的个数，然后交叉相乘取和就能够了

代码例如以下：

#include<cstdio>

#include<cstring>

#include<string>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 1e5+10;

int n;

int p[N], c[N], li[N], la[N], ri[N], ra[N];

inline int Lowbit(int x){ return x&(-x); } 

void change(int u, int x)

{

	while(u < N)

	{

		c[u] += x;

		u += Lowbit(u);

	}

} 

int get_sum(int x)

{

	int ans = 0;

	for(int i = x; i > 0; i -= Lowbit(i))

	{

		ans += c[i];

	}

	return ans;

}

int main()

{

	int t;

	scanf("%d", &t);

	while(t--)

	{

		memset(c, 0, sizeof(c));

		scanf("%d", &n);

		for(int i = 1; i <= n; i++)

		{

			scanf("%d", &p[i]);

			int cnt = get_sum(p[i]);

			li[i] = cnt; // i点左边比它小的

			la[i] = i - cnt - 1; //i点左边比它大的

			change(p[i], 1);

		}

		memset(c, 0, sizeof(c));

		for(int i = n; i > 0; i--)

		{

			int cnt = get_sum(p[i]);

			ri[i] = cnt; // i点右边比它小的

			ra[i] = n - i - cnt; //i点右边比它大的

			change(p[i], 1);

		}

		ll ans = 0;

		for(int i = 1; i <= n; i++)

		{

			ans += li[i] * ra[i] + la[i] * ri[i];

		}

		printf("%I64d\n", ans);

	}

	return 0;

}