Sequence II

1
5
1 3 2 4 5

4

要统计四元组的数量我们可以通过枚举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，那么这个可以通过用树状数组询问前缀和来实现.
时间复杂度是O(nlogn).

//1684MS	1840K
#include<stdio.h>
#include<string.h>
#define ll __int64
#define N 50007
int a[N],pre[N],suf[N],C[N];//pre记录前缀，suf记录后缀
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos,int val)
{
    while(pos<N)
    {
        C[pos]+=val;
        pos+=lowbit(pos);
    }
}
int getsum(int x)
{
    int result=0;
    while(x>0)
    {
        result+=C[x];
        x-=lowbit(x);
    }
    return result;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(C,0,sizeof(C));
        for(int i=1;i<=n;i++)//计算前缀的个数
        {
            pre[i]=getsum(a[i]);
            add(a[i],1);
        }
        memset(C,0,sizeof(C));
        for(int i=n;i>=1;i--)//计算后缀的个数
        {
            suf[i]=n-i-getsum(a[i]);//倒着输入，第i个数后面有n-i个数，再看看这n-i个数中是不是存在比a[i]小的
            add(a[i],1);
        }
        ll ans=0,p=0;//p代表前缀的总个数
        for(int i=1;i<n;i++)//枚举c的位置
        {
            ans+=suf[i]*p;
            p+=pre[i];
        }
        printf("%I64d\n",ans);
    }
}