记录编号	133276	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	RP++	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2014-10-27 18:41:45	内存使用	3.62 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

struct node{
	int In_Pos;
	int nData;
	int New_Pos;
}f[100001],t[100001];

int pos[100001]={0};
int nTmp[100001]={0};
long long ans=0;

int comp(const node&a,const node&b)
{
	return a.nData<b.nData;
}

int cmp(const node&a,const node&b)
{
	return a.In_Pos<b.In_Pos;
}

void MergoSort(int ,int );

int main()
{
	freopen("MatchNOIP2013.in","r",stdin);
	freopen("MatchNOIP2013.out","w",stdout);
	int sum;
	scanf("%d",&sum);
	for(int i=1;i<=sum;i++)
	{
		scanf("%d",&f[i].nData);
		f[i].In_Pos=i;
	}
	for(int i=1;i<=sum;i++)
	{
		scanf("%d",&t[i].nData);
		t[i].In_Pos=i;
	}
	sort(f+1,f+sum+1,comp);
	for(int i=1;i<=sum;i++)f[i].New_Pos=i;
	sort(t+1,t+sum+1,comp);
	for(int i=1;i<=sum;i++)t[i].New_Pos=i;
	sort(t+1,t+sum+1,cmp);
	sort(f+1,f+sum+1,cmp);
	int num[100001]={0};
	for(int i=1;i<=sum;i++)num[f[i].New_Pos]=i;
	for(int i=1;i<=sum;i++)pos[i]=num[t[i].New_Pos];
	MergoSort(1,sum);
	printf("%d",ans%99999997);
}

inline void MergoSort(int l,int r)
{
	if(l==r)return ;
	int mid=(l+r)>>1;
	MergoSort(l,mid);
	MergoSort(mid+1,r);
	int i=l;
	int j=mid+1;
	int tot=l;
	while(i<=mid&&j<=r)
	{
		if(pos[i]<=pos[j])
		{
			nTmp[tot]=pos[i];
			tot++;
			i++;
		}
		else
		{
			nTmp[tot]=pos[j];
			tot++;
			j++;
			ans+=mid-i+1;
		}
	}
	while(i<=mid)
	{
		nTmp[tot]=pos[i];
		i++;
		tot++;
	}
	while(j<=r)
	{
		nTmp[tot]=pos[j];
		j++;
		tot++;
	}
	for(int i=l;i<=r;i++)
	{
		pos[i]=nTmp[i];
	}
}