Problem Description

Given a sequence A with length n,count how many quadruple (a,b,c,d) satisfies: a≠b≠c≠d,1≤a<b≤n,1≤c<d≤n,Aa<Ab,Ac>Ad.

 

Input

The input consists of multiple test cases. 
Each test case begin with an integer n in a single line.

The next line contains n integers A1,A2⋯An.
1≤n≤50000
0≤Ai≤1e9

 

Output

For each test case,output a line contains an integer.

 

Sample Input

 

Sample Output

 

题意肯简单；

 

思路：先将输入的n个数进行离散化处理得到A[]，使每个数小于50000，然后就可以使用树状数组求出 在第i个数时 在1~i-1中比A[i]大的个数、在1~i-1中比A[i]小的个数、在i+1~n中比A[i]小的个数、在i+1~n中比A[i]大的个数，即得到对应数组a1[]、b1[]、a2[]、b2[]  ; 很容易用树状数组求出A[]数组中逆序数的个数num1及上升的数对的个数num2,sum=num1*num2, 再一个循环sum=sum-a1[i]*a2[i]-b1[i]*b2[i]-a1[i]*b1[i]-a2[i]*b2[i],最后sum即为结果;

 

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <map>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const int N=;

typedef long long LL;

LL Scan()///输入外挂

{

    LL res=,ch,flag=;

    if((ch=getchar())=='-')

        flag=;

    else if(ch>=''&&ch<='')

        res=ch-'';

    while((ch=getchar())>=''&&ch<='')

        res=res*+ch-'';

    return flag?-res:res;

}

void Out(LL a)///输出外挂

{

    if(a>)

        Out(a/);

    putchar(a%+'');

}

long long A[];

long long B[];

map<long long,long long>p;

long long c[N];

long long a1[N],a2[N];  ///小;

long long b1[N],b2[N];  ///大;

long long Lowbit(long long t)

{

    return t&(t^(t-));

}

void update(long long x)

{

    while(x>)

    {

        c[x]++;

        x -= Lowbit(x);

    }

}

long long Sum(long long li)

{

    long long sum=;

    while(li<N)

    {

        sum+=c[li];

        li=li+Lowbit(li);

    }

    return sum;

}

int main()

{

    long long n;

    long long sum;

    while(scanf("%lld",&n)!=EOF)

    {

        sum=;

        for(int i=;i<n;i++)

        {

            A[i] = Scan();

            B[i]=A[i];

        }

        sort(B,B+n);

        long long tot=,pre=;

        for(int i=;i<n;i++)  ///离散化，

        {

            if(B[i]==pre)

                B[i]=tot;

            else

            {

                pre=B[i];

                B[i]=++tot;

                p[pre]=tot;

            }

        }

        for(int i=;i<n;i++)

            A[i]=p[A[i]];

        long long num1=;

        long long num2=;

        memset(c,,sizeof(c));

        for(int i=;i<n;i++)

        {

            num1+=Sum(A[i]+);

            update(A[i]);

        }

        memset(c,,sizeof(c));

        for(int i=n-;i>=;i--)

        {

            num2+=Sum(A[i]+);

            update(A[i]);

        }

        sum=num1*num2;

        ///cout<<"num1: "<<num1<<" num2: "<<num2<<" sum: "<<sum<<endl;

        memset(a1,,sizeof(a1));

        memset(a2,,sizeof(a2));

        memset(b1,,sizeof(b1));

        memset(b2,,sizeof(b2));

        memset(c,,sizeof(c));

        for(int i=;i<n;i++)

        {

            a1[i]=Sum(N-A[i]+);

            update(N-A[i]);

        }

        memset(c,,sizeof(c));

        for(int i=n-;i>=;i--)

        {

            a2[i]=Sum(N-A[i]+);

            update(N-A[i]);

        }

        memset(c,,sizeof(c));

        for(int i=;i<n;i++)

        {

            b1[i]=Sum(A[i]+);

            update(A[i]);

        }

        memset(c,,sizeof(c));

        for(int i=n-;i>=;i--)

        {

            b2[i]=Sum(A[i]+);

            update(A[i]);

        }

        for(int i=;i<n;i++)

        {

            sum-=a1[i]*a2[i];

            sum-=a1[i]*b1[i];

            sum-=a2[i]*b2[i];

            sum-=b1[i]*b2[i];

        }

        Out(sum);

        puts("");

    }

    return ;

}