原题大意

给出一个长度为n的整数序列V，要求输出有多少个四元组{a,b,c,d}。
满足1 <=a < b <= n,1 <=c < d <= n,a!=b!=c!=d 且 VaVd

算法分析

先用树状数组处理每个位置(离散化处理，否则10^9存不下)左边比它大或小的有几个，右边比它大或小的有几个，算出这个序列分正序数和逆序数，并乘起来，然后去掉a==c,a==d,b==d,b==d,四种情况的个数。

程序代码

#include<iostream>  
#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
typedef long long ll;  
ll num,a[50005],zx[50005],zd[50005],yx[50005],yd[50005],C[50005],b[50005];  
ll lowbit(ll x){  
    return x&-x;  
}  
void change(ll pos,ll x){  
    while(pos<=50006){  
        C[pos]+=x;  
        pos+=lowbit(pos);  
    }  
}  
ll sum(ll n){  
    ll ss=0;  
    while(n>0){  
        ss+=C[n];  
        n-=lowbit(n);  
    }  
    return ss;  
}  
int main(){  
    ll n;  
    while(scanf("%lld",&n)!=EOF){  
        ll i,j;  
        for(i=1;i<=n;i++){  
            scanf("%lld",&a[i]);  
            b[i]=a[i];  
        }  
        memset(C,0,sizeof(C));  
        sort(b+1,b+1+n);  
        num=unique(b+1,b+1+n)-b-1;//离散化  
        ll sum1=0,sum2=0;  
        for(i=1;i<=n;i++){  
            ll t=lower_bound(b+1,b+1+n,a[i])-b;//寻找当前位置离散化后的值  
            change(t,1);  
            zx[i]=sum(t-1);//左边比它小的  
            zd[i]=i-sum(t);//左边比它大的  
        }  
        memset(C,0,sizeof(C));  
        for(i=n;i>=1;i--){  
            ll t=lower_bound(b+1,b+1+n,a[i])-b;  
            change(t,1);  
            yx[i]=sum(t-1);  
            yd[i]=(n-i+1)-sum(t);  

            //这里的sum1和sum2的累加也可以写在上面zx，zd处，结果不影响。
            sum1+=yx[i];//右边比它小的  
            sum2+=yd[i];//右边比它大的  
        }  
        ll ans=sum1*sum2;//正序数*逆序数  
        for(i=1;i<=n;i++){//去重  
            ans-=yx[i]*yd[i];  
            ans-=zx[i]*yx[i];  
            ans-=zd[i]*yd[i];  
            ans-=zx[i]*zd[i];  
        }  
        printf("%lld\n",ans);  
    }  
    return 0;  
}