题目大意：

给出一个元素个数为n的序列num[]，元素值两两不同，问序列中满足 num[i]<num[j]<num[k] 或 num[i]>num[j]>num[k] （i<j<k） 的三元子序列的个数是多少。

思路：

构想一个虚拟的hash数组，各项值默认为0，若元素num[i]存在，则hash[num[i]]=1。

如此以来，若想知道比num[i]小的元素的个数，只需要求hash[1…num[i]-1]的和即可。而这个和可以由树状数组c[]来维护。因此hash数组并不需要实际定义。

任意时刻，执行树状数组的sum(num[i]-1)操作，即求取hash[1…num[i]-1]的和，便可知当前比num[i]小的元素的数量。

定义a[i]为从元素1到元素i-1之间，小于元素i的元素的数量，b[i]为从元素i+1到元素n之间，小于元素i的元素的数量。那么a[j]*(n-j-b[j])便是所有以元素j为中间元素的三元升序序列的数量。求取降序三元序列的方法同理。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define datasize 100000
//datasize即数据范围，在这里并不是元素数量，而是元素值域。 
int a[20000+1],b[20000+1],c[datasize+1],num[datasize+1];
//num[]用于存储元素。 
//a[i]表示从元素1到元素i-1之间，小于元素i的元素的数量。
//b[i]表示从元素i+1到元素n之间，小于元素i的元素的数量。 
//c[]为树状数组。 
int lowbit(int x)
{
	return x&-x;
}
int sum(int end)
//求取虚拟hash数组1至end的和。 
{
	int s=0;
	while(end>0)
	{
		s+=c[end];
		end-=lowbit(end);
	}
	return s;
}
void modify(int pos)
//在虚拟hash数组的第pos位上+1。 
{
	while(pos<=datasize)
	{
		c[pos]++;
		pos+=lowbit(pos);
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		int n;
		scanf("%d",&n);
		for(int j=1;j<=n;j++)
			scanf("%d",&num[j]);
		memset(c,0,sizeof(c));
		for(int j=1;j<=n;j++)
		{
			a[j]=sum(num[j]-1);
			//为a[]赋值 
			modify(num[j]);
		}
		memset(c,0,sizeof(c));
		for(int j=n;j>=1;j--)
		{
			b[j]=sum(num[j]-1);
			//为b[]赋值 
			modify(num[j]);
		}
		long long res=0;
		for(int j=1;j<=n;j++)
			res+=a[j]*(n-j-b[j])+(j-1-a[j])*b[j];
			//n-j表示元素j+1到n之间元素的数量，n-j-b[j]即是元素j+1到n之间大于元素j的元素数量。
			//a[j]*(n-j-b[j])便是所有以元素j为中间元素的三元升序序列的数量。
			//(j-1-a[j])*b[j]同理。 
		printf("%I64d\n",res);
	}
}