http://acm.hdu.edu.cn/showproblem.php?pid=5147
Problem Description
Long long ago, there is a sequence A with length n. All numbers in this sequence is no smaller than 1 and no bigger than n, and all numbers are different in this sequence.
Please calculate how many quad (a,b,c,d) satisfy:
1. 1≤a<b<c<d≤n
2. Aa<Ab
3. Ac<Ad
Please calculate how many quad (a,b,c,d) satisfy:
1. 1≤a<b<c<d≤n
2. Aa<Ab
3. Ac<Ad
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with a line contains an integer n.
The next line follows n integers A1,A2,…,An.
[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <= Ai <= n
Each test case begins with a line contains an integer n.
The next line follows n integers A1,A2,…,An.
[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <= Ai <= n
Output
For each case output one line contains a integer,the number of quad.
Sample Input
1 5 1 3 2 4 5
Sample Output
4
/**
hdu5147 树状数组
解题思路：
要统计四元组的数量我们能够通过枚举c，然后统计区间[1,c-1]有多少二元组(a,b)满足a<b且Aa<Ab。以及统计出区间[c+1,n]有多少d满足Ac<Ad，
依据乘法原理，把这两项乘起来就能够统计到答案里了.然后我们来处理子问题：区间[1,c-1]内有多少二元组(a,b).那么我们能够枚举b，然后统计
区间[1,b-1]内有多少a满足Aa<Ab，那么这个能够通过用树状数组询问前缀和来实现.
详细实现：b[i]和c[i]中存储的分别为以i结尾的Ax<Ay的对数和从i+1到n中Ax<Ay的对数，二者相乘即为答案。
时间复杂度是O(nlogn).
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long LL;
int C[100005],b[100005],c[100005],a[100005];
int n;
int lowbit(int x)
{
return x&(-x);
}
int sum(int x)
{
int ret=0;
while(x>0)
{
ret+=C[x];
x-=lowbit(x);
}
return ret;
}
void add(int x,int d)
{
while(x<=n)
{
C[x]+=d;
x+=lowbit(x);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(C,0,sizeof(C));
for(int i=1;i<=n;i++)
{
b[i]=sum(a[i]);
add(a[i],1);
}
memset(C,0,sizeof(C));
for(int i=n;i>=1;i--)
{
c[i]=sum(n)-sum(a[i])+c[i+1];
add(a[i],1);
}
LL ans=0;
for(int i=2;i<=n-2;i++)
{
LL t1=b[i];
LL t2=c[i+1];
ans+=t1*t2;
}
printf("%I64d\n",ans);
}
return 0;
}
