记录编号	229413	评测结果	AAAAAAAAAA
题目名称	[尼伯龙根之歌] 精灵魔法	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.446 s
提交时间	2016-02-20 09:44:08	内存使用	1.31 MiB

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=100010;
int tree[maxn],n;
struct Tree
{
	int speed,location;
}a[maxn];
int _sum(int x)
{
	int sum=0;
	for(int i=x;i<=n;i+=(i&(-i))) sum+=tree[i];
	return sum;
}
void Update(int x,int y) 
{	
	for(int i=x;i>0;i-=(i&(-i)))
	{
		tree[i]+=y;
	} 
}
int cmp1(const Tree&a,const Tree&b)
{
	return a.location<b.location;
}
int cmp2(const Tree&a,const Tree&b)
{
	if(a.speed==b.speed)
	{
		return a.location<b.location;
	}
	else return a.speed<b.speed;
}
void Init() 
{
	long long sum=0;
	memset(tree,0,sizeof(tree));
	int b[maxn];
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].location);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].speed);
	}
	sort(a+1,a+1+n,cmp1);
	for(int i=1;i<=n;i++)a[i].location=i;
	sort(a+1,a+1+n,cmp2);
	int k;
	for(int i=1;i<=n;i++) 
	{
		b[a[i].location]=i;
	}
	for(int i=1;i<=n;i++)
	{
		k=_sum(b[i]);
		sum+=k;
		Update(b[i],1);
	}
	printf("%lld",sum);
}
int main()
{	
	freopen("alfheim.in","r",stdin);
	freopen("alfheim.out","w",stdout);
	scanf("%d",&n);
	Init();
}