记录编号	253324	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.112 s
提交时间	2016-04-21 21:44:48	内存使用	2.99 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
//#include"debug.h"
using namespace std;

const int maxl=100010;
int n,a[maxl],b[maxl],c[maxl],d[maxl],e[maxl],f[maxl],ra[maxl],i,j;
long long ans;
//a and b are original data. ra[i] means the ranking of a.  
bool cmpc(const int x,const int y){
	return a[x]<a[y];
}
bool cmpd(const int x,const int y){
	return b[x]<b[y];
}
void mergesort(int l,int r){
	int m=(l+r)/2;
	if (l!=r){
		mergesort(l,m);
		mergesort(m+1,r);
	}
	int i=l,j=m+1,p=l;
	while (i<=m&&j<=r)
	if (e[i]<=e[j]) f[p++]=e[i++];
	else{
		ans+=m+1-i;f[p++]=e[j++];
	}
	for (;i<=m;i++) f[p++]=e[i];
	for (;j<=r;j++) f[p++]=e[j];
	for (i=l;i<=r;i++) e[i]=f[i];
}

int main()
{
	freopen("MatchNOIP2013.in","r",stdin);
	freopen("MatchNOIP2013.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	for (i=1;i<=n;i++) scanf("%d",&b[i]);
	for (i=1;i<=n;i++) c[i]=d[i]=i;
	sort(c+1,c+n+1,cmpc);
	for (i=1;i<=n;i++) ra[c[i]]=i;
	sort(d+1,d+n+1,cmpd);
	
	for (i=1;i<=n;i++) e[i]=d[ra[i]];
	mergesort(1,n);
	cout<<ans%99999997<<endl;
	return 0;
}