题目大意：
给出一个元素个数为n的序列num[]，元素值两两不同，问序列中满足 num[i]<num[j]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
#include
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=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);
}
}