记录编号	229632	评测结果	AAAAAAAAAA
题目名称	[尼伯龙根之歌] 精灵魔法	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.421 s
提交时间	2016-02-20 14:11:07	内存使用	12.46 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000100;int n;long long ans=0;
int a[maxn]={0},c[maxn]={0};
struct Node{
	int num,data;
	Node(){
		num=data=0;
	}
	bool operator <(const Node&a)const{
		return num<a.num;
	}
}b[maxn];
void hebing(int,int,int);
void Devi(int,int);
int main()
{
	freopen("alfheim.in","r",stdin);
	freopen("alfheim.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i].num);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i].data);
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
	{
		a[i]=b[i].data;
	}
	Devi(1,n);
	printf("%lld",ans);
}
void Devi(int l,int r){
	if(l>=r) return;
	int mid=(l+r)>>1;
	Devi(l,mid);
	Devi(mid+1,r);
	hebing(l,mid,r);
}
void hebing(int l,int mid,int r)
{
	int k=l,i=l,j=mid+1;
	while(k<=r){
		if(i>mid){
			c[k]=a[j];j++;k++;
			continue;
				}
				if(j<=r&&a[j]<a[i])
				{
				c[k]=a[j];k++;j++;ans+=mid-i+1;continue;
				}
				c[k]=a[i];i++;k++;}
	for(int i=l;i<=r;i++) a[i]=c[i];
}