UVA 1428 Ping pong (UVALive 4329, POJ 3928, HDU 2492, Regionals 2008 >> Asia - Beijing)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100000

int tree[MX+2], mxl[20002], mnl[20002], mxr[20002], mnr[20002], arr[20002];

void insert(int x)
{
    while(x<=MX)
    {
        tree[x]++;
        x += x & -x;
    }
return;
}

int read(int x)
{
    int ret=0;
    while(x)
    {
        ret+=tree[x];
        x-= x & -x;
    }
return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n, m, x, y, a, b, c, pos;
    string s;
    cin>>tc;
    while(tc--)
    {
        CLR(tree);
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            arr[i]=x;
            mnl[i]=read(x);
            mxl[i]=i-mnl[i];
            insert(x);
        }
        CLR(tree);

        for(int i=n-1;i>=0;i--)
        {
            x=arr[i];
            mnr[i]=read(x);
            mxr[i]=n-1-i-mnr[i];
            insert(x);
        }
        long long ans = 0;
        for(int i=0;i<n;i++) //cout<<mxr[i]<<endl;
            ans += mnl[i]*mxr[i] + mnr[i] * mxl[i];
        cout<< ans <<"\n";
    }
return 0;
}