记录编号	49807	评测结果	AAAAAAAAAA
题目名称	三元数对	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2012-11-09 13:01:51	内存使用	2.34 MiB

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
long long a[50000][2],b,c,d,l,s,t[50000][2],n[50000][2];
void guibing(long long p,long long q)
{
	int i,j,k;
	if (p>=q) return;
	guibing(p,(p+q)/2);
	guibing((p+q)/2+1,q);
	k=p;
	i=p;
	j=(p+q)/2+1;
	while (k<=q) 
	{
		if (a[i][0]<a[j][0]&&i<=(p+q)/2&&j<=q)
		{
			t[k][0]=a[i][0];
			t[k][1]=a[i][1];
			n[a[i][1]][1]+=q-j+1;
			k++;
			i++;
		}
			else if (a[i][0]>=a[j][0]&&i<=(p+q)/2&&j<=q)
				 {
					t[k][0]=a[j][0];
					t[k][1]=a[j][1];
					n[a[j][1]][0]+=i-p;
					k++;
					j++;
				 }
					/* else if (a[i][0]==a[j][0]&&i<=(p+q)/2&&j<=q)
					{
						t[k][0]=a[j][0];
						t[k][1]=a[j][1];
						n[a[j][1]][0]+=i-p;
						k++;
						j++;
					}*/
						else if (i>(p+q)/2)
							 {
								 t[k][0]=a[j][0];
								 t[k][1]=a[j][1];
								 n[a[j][1]][0]+=i-p;
								 k++;
								 j++;
							 }	
								else if (j>q)
								{ 
									t[k][0]=a[i][0];
									t[k][1]=a[i][1];
									k++;
									i++;
								}
	}
	for (i=p;i<=q;i++) 
	{
		a[i][0]=t[i][0];
		a[i][1]=t[i][1];
	}
}
int main(void)
{
    freopen("three.in","r",stdin);
    freopen("three.out","w",stdout);
	scanf("%lld",&b);
	for (c=0;c<b;c++) 
	{
		scanf("%d",&a[c][0]);
		a[c][1]=c+1;
	}
	guibing(0,b-1);
	for (c=0;c<b;c++) s+=n[c][0]*n[c][1];
	printf("%lld",s);
	fclose(stdin);
    fclose(stdout);
    return 0;
}