记录编号	62404	评测结果	AAAAAAAAAA
题目名称	排序工作量-加强版	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2013-06-26 16:14:15	内存使用	0.89 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<stack>
#include<vector>
#include<fstream>
using namespace std;
const int SIZEN=50010;
int n;
class NODE{
public:
	int data;
	int pos;
}s[SIZEN];
bool operator < (NODE a,NODE b){
	return a.data>b.data;
}
int sum[SIZEN]={0};
void read(void){
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) scanf("%d",&s[i].data),s[i].pos=i;
	for(i=1;i<=n;i++) sum[i]=0;
}
int lowbit(int x){
	return x&(-x);
}
void change(int x,int num){
	while(x<=n){
		sum[x]+=num;
		x+=lowbit(x);
	}
}
int psum(int x){
	int ans=0;
	while(x>0){
		ans+=sum[x];
		x-=lowbit(x);
	}
	return ans;
}
void work(void){
	sort(s+1,s+1+n);
	int last=1,i=1,j;
	int ans=0;
	for(i=1;i<=n;i++){
		ans+=psum(s[i].pos-1);
		if(i==n||s[i].data!=s[i+1].data){
			for(j=last;j<=i;j++) change(s[j].pos,1);
			last=i+1;
		}
	}
	printf("%d\n",ans);
}
int main(){
	freopen("px.in","r",stdin);
	freopen("px.out","w",stdout);
	read();
	work();
	return 0;
}