记录编号	39358	评测结果	AAAAAAAAAA
题目名称	数列	最终得分	100
用户昵称	ZhouHang	是否通过	通过
代码语言	C++	运行时间	0.134 s
提交时间	2012-07-09 15:37:04	内存使用	2.12 MiB

/*Task : b
 *Data : 2.19 
 *Sol  : 线段树
 *Auth : Zhou Hang
*/
 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int MaxNum=40000;
const int MaxN=51000;
const int oo=1000000000;
 
int a[4*MaxNum+100][2];
int m,n,ans,i,x,y,ch;
int l[MaxN],r[MaxN],h[MaxN];
 
void updata(int l,int r,int root)
{
    if ((y<l)||(x>r)) return;
     
    if ((x<=l)&&(y>=r))
    {
        a[root][0]++; a[root][1]++;
        return;
    }
     
    int mid=(l+r)/2;
    //必须是临时变量，避免递归时改变
     
    //left child
    a[root*2][0]+=a[root][1]; 
    a[root*2][1]+=a[root][1];
    //right child
    a[root*2+1][0]+=a[root][1];
    a[root*2+1][1]+=a[root][1];
    //itself
    a[root][1]=0;
     
    updata(l,mid,root*2);
    updata(mid+1,r,root*2+1);
    //change Sum
    a[root][0]=a[root*2][0]+a[root*2+1][0];
}
 
int find(int l,int r,int root)
{
    if ((y<l)||(x>r)) return 0;
    if ((x<=l)&&(y>=r)) return a[root][0];
     
    int mid=(l+r)/2;
    //left child
    a[root*2][0]+=a[root][1]; 
    a[root*2][1]+=a[root][1];
    //right child
    a[root*2+1][0]+=a[root][1];
    a[root*2+1][1]+=a[root][1];
    //itself
    a[root][1]=0;
     
    int m1=find(l,mid,root*2);
    int m2=find(mid+1,r,root*2+1);
     
    return m1+m2;
}
 
int main()
{
     
    freopen("queueb.in","r",stdin);
    freopen("queueb.out","w",stdout);
     
    scanf("%d",&n);
     
    int maxh = -1;
    for (int i=1; i<=n; i++) {
        scanf("%d",&h[i]);
        if (h[i]>maxh) maxh = h[i];
    }
     
    for (int i=1; i<=n; i++) {
        x = y = h[i];
        updata(0,maxh,1);
        x = 0; y = h[i]-1;
        l[i] = find(0,maxh,1);
    }
    memset(a,0,sizeof(a));
    for (int i=n; i>=1; i--) {
        x = y = h[i];
        updata(0,maxh,1);
        x = 0; y = h[i]-1;
        r[i] = find(0,maxh,1);
    }
     
    long long ans = 0;
    for (int i=1; i<=n; i++)
        ans += (long long)l[i]*r[i];
     
    cout<<ans<<endl;
     
    fclose(stdin); fclose(stdout);
     
}