记录编号	185560	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.094 s
提交时间	2015-09-07 19:05:19	内存使用	2.69 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
const int max_int=1061109567;
const int maxn=100010;
const int maxm=30;
const int mod=1000;

struct node
{
    int val;
    int pos;
    node() {val=pos=0;}
} a[maxn],b[maxn],t[maxn];

int Ans1[maxn];
int Ans2[maxn];

void Merge(node x[],int l,int m,int r,int Ans[])
{
    int i=l,j=m+1;
    int k=0;
    int cnt=0;
    while(i<=m&&j<=r)
    {
        if(x[i].val>=x[j].val)
        {
            Ans[x[j].pos]+=cnt;
            t[k++]=x[j++];
        }
        else
        {
            t[k++]=x[i++];
            cnt++;
        }
    }
    while(i<=m) t[k++]=x[i++];
    while(j<=r)
    {
        Ans[x[j].pos]+=cnt;
        t[k++]=x[j++];
    }
    for(int i=0;i<k;i++) x[l+i]=t[i];
}

void Merge_sort(node x[],int l,int r,int Ans[])
{
    if(l==r) return;
    int m=(l+r)/2;
    Merge_sort(x,l,m,Ans);
    Merge_sort(x,m+1,r,Ans);
    Merge(x,l,m,r,Ans);
}

int main()
{
    freopen("queueb.in","r",stdin);
    freopen("queueb.out","w",stdout);
    //clock_t st=clock();
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
        a[i].pos=i;
        b[n-i+1]=a[i];
    }
    Merge_sort(a,1,n,Ans1);
    Merge_sort(b,1,n,Ans2);
    /*for(int i=1;i<=n;i++) printf("%d ",Ans1[i]);
    printf("\n");
    for(int i=1;i<=n;i++) printf("%d ",Ans2[i]);
    printf("\n");*/
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=(Ans1[i]*Ans2[i]);
    }
    printf("%lld\n",ans);
    //clock_t ed=clock();
    //printf("\nTime used : %.7lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}