记录编号	268367	评测结果	AAAAAAAAAA
题目名称	1144.[尼伯龙根之歌] 精灵魔法	最终得分	100
用户昵称	Hzoi_Yniverse	是否通过	通过
代码语言	C++	运行时间	0.240 s
提交时间	2016-06-12 14:45:15	内存使用	1.84 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct Node{
	int data,num;
}a[maxn];
bool comp1(const Node &a,const Node &b){
	return a.data<b.data;
}
bool comp2(const Node &a,const Node &b){
	return a.num<b.num;
}
long long ans;
long long c[maxn],n;
long long Getsum(int);
void Insert(int);
int lowbit(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",&a[i].num);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].data);
	sort(a+1,a+n+1,comp1);
	int last=0;
	for(int i=1;i<=n;i++){
		int x=a[i].data;
		if(a[i].data==last)a[i].data=a[i-1].data;
		else a[i].data=i;
		last=x;
	}
	sort(a+1,a+n+1,comp2);
	for(int i=1;i<=n;i++){
		ans+=Getsum(a[i].data+1);
		Insert(a[i].data);
	}
	printf("%lld",ans);
	return 0;
}
long long Getsum(int x){
	long long tot=0;
	for(int i=x;i<=n;i+=lowbit(i)){
		tot+=c[i];
	}
	return tot;
}
void Insert(int x){
	for(int i=x;i>0;i-=lowbit(i)){
		c[i]++;
	}
}
int lowbit(int x){
	return x&-x;
}