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