http://codeforces.com/problemset/problem/61/E

题意是求 i<j<k && a[i]>a[j]>a[k] 的对数

会树状数组求逆序数的话，这个推一下就能出结果：

做法：

1、离散化，由于a[i]能够达到1e9

2、插入a[i]的时候，记录x[i]=i-sum(a[i]); a[i]之前比a[i]大的有x[i]个

3、插入完毕后，求a[i] 之后比a[i]小的数的个数y[i]

ans=segma(x[i]*y[i])   注意x[i]*y[i]会超出int  由于这wa了一次

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <iomanip>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdout)

const ll ll_INF = ((ull)(-1))>>1;

const double EPS = 1e-8;

const int INF = 100000000;

const int MAXN  = 1e6+100;

ll x[MAXN],y[MAXN];

int a[MAXN],tmp[MAXN];

ll c[MAXN];

int n;

inline int lowb(int x) {return x&(-x);}

void update(int x, int d)

{

    while(x<=n)

    {

        c[x]+=d;

        x+=lowb(x);

    }

}

ll sum(int x)

{

    ll ret=0;

    while(x>0)

    {

        ret+=c[x];

        x-=lowb(x);

    }

    return ret;

}

bool cmp(const int i, const int j)

{

    return a[i]<a[j];

}

void dis()

{

    sort(tmp+1,tmp+1+n,cmp);

    int tt=0,pre=a[tmp[1]]-1;

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

    {

        if(pre!=a[tmp[i]])

        {

            pre=a[tmp[i]];

            a[tmp[i]]=++tt;

        }

        else

            a[tmp[i]]=tt;

    }

}

int main()

{

    //IN("B.txt");

    ll ans=0;

    while(~scanf("%d",&n))

    {

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

        {

            scanf("%d",&a[i]);

            tmp[i]=i;

        }

        dis();

        /////////////////

        /*for(int i=1;i<=n;i++)

        {

            printf("a[%d]=%d\n",i,a[i]);

        }*/

        /////////////////

        CL(c,0);

        ans=0;

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

        {

            update(a[i],1);

            x[i]=i-sum(a[i]);//a[i]之前比a[i]大的有`x[i]个

            y[i]=sum(a[i]-1);//a[i]之前比a[i]小的数

        }

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

        {

            y[i]=sum(a[i]-1)-y[i];//a[i] 之后比a[i]小的数的个数

            ans+=x[i]*y[i];

        }

        /////////////////

       /* for(int i=1;i<=n;i++)

            printf("i=%d x=%d y=%d\n",i,x[i],y[i]);*/

        /////////////////

        printf("%I64d\n",ans);

    }

    return 0;

}