记录编号	114430	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	高哥	是否通过	通过
代码语言	C++	运行时间	0.505 s
提交时间	2014-07-29 15:16:48	内存使用	19.39 MiB

/*离散化+逆序对：
1.先将原始数据按大小离散化成1，2，3，4……
  如：
  原始数据：8 5 7 9 10 
  离散化后：3 1 2 4 5
  两组数据都要这样做；
2.然后对第一组数据离散后的数组标上位置数：
  如（前面的例子）：3 1 2 4 5
  标上位置数后：    1 2 3 4 5
3.把第二组数据（离散化后）映射成第一组数据
  如第二组数据离散化后为： 5 3 1 2 4
  根据第一组数据映射后为： 5 1 2 3 4
4.最后对第二组数据（映射后的）进行逆序对即可；
  */ 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define INF 1000100
#define c 99999997
using namespace std;
map<int,int> pre1;
map<int,int> pre2;
map<int,int> pre3;
int a[INF],a1[INF],b[INF],b1[INF],n; 
int p[INF];
long long ans;
int megersort(int l,int mid,int r)
{
	int i=l,j=mid+1;
	int k=i;
	while(i<=mid && j<=r)
	{
		if(b1[i]>b1[j])
		{
		  p[k++]=b1[j++];
		  ans+=mid-i+1;
		  ans%=c;
		}
		else
		  p[k++]=b1[i++];
	}
	while(i<=mid)
	  p[k++]=b1[i++];
	while(j<=r)
	  p[k++]=b1[j++];
	for(int i=l;i<=r;i++)
	  b1[i]=p[i];
}
void meger(int l,int r)
{
	if(l==r)
	 return ;
	int mid=(l+r)>>1;
	meger(l,mid);
	meger(mid+1,r);
	megersort(l,mid,r);
}
int input()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  {scanf("%d",&a[i]);a1[i]=a[i];}
	for(int i=1;i<=n;i++)
	  {scanf("%d",&b[i]);b1[i]=b[i];}
}
int work()
{
	input();
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	
	for(int i=1;i<=n;i++)
	{
		pre1[a[i]]=i;
		pre2[b[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		a1[i]=pre1[a1[i]];
		b1[i]=pre2[b1[i]];
	}// 对两组数据离散化操作 
	
	for(int i=1;i<=n;i++)
		pre3[a1[i]]=i;   //对第一组数据（离散化后）标上位置数 
	for(int i=1;i<=n;i++)
	    b1[i]=pre3[b1[i]];
	// 把第二组数据映射 

	meger(1,n);//对第二组数据逆序对 
	printf("%lld\n",ans%c);
	
}
int main()
{
	 freopen("MatchNOIP2013.in","r",stdin);
	 freopen("MatchNOIP2013.out","w",stdout);
	 work();
	 return 0;
}