记录编号	133320	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	·	是否通过	通过
代码语言	C++	运行时间	0.995 s
提交时间	2014-10-27 19:40:23	内存使用	8.71 MiB

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

using namespace std;

long long c[100001],w[100001];
int n;

long long lowbit(long long x)
{
	return x&(-x);
}

long long sum(long long x)
{
	long long ans=0;
	while(x>0)
	{
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}

void add(long long x,long long y)
{
	while(x<=n)
	{
		c[x]+=y;
		x+=lowbit(x);
	}
}

struct jiegouti
{
	long long a;
	long long k;
	long long num;
}T[100001],F[100001],P[100001];

long long paixu(jiegouti a,jiegouti b)
{
	if(a.a>b.a) return 1;
	if(a.a==b.a)
	{
		if(a.num>b.num) return 1;
		return 0;
	}
	return 0;
}

long long huanyuan(jiegouti a,jiegouti b)
{
	return a.num<b.num;
}

int main()
{
	freopen("MatchNOIP2013.in","r",stdin);
	freopen("MatchNOIP2013.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>T[i].a;
	for(int i=1;i<=n;i++)	cin>>F[i].a;
	for(int i=1;i<=n;i++)	T[i].num=i,F[i].num=i;
	
	sort(T+1,T+n+1,paixu);
	sort(F+1,F+n+1,paixu);
	
	for(int i=1;i<=n;i++)	T[i].k=i,F[i].k=i;
	
	sort(T+1,T+n+1,huanyuan);
	sort(F+1,F+n+1,huanyuan);
	
	for(int i=1;i<=n;i++)	w[T[i].k]=i;

	for(int i=1;i<=n;i++)	P[i].a=w[F[i].k];
	
	for(int i=1;i<=n;i++)	P[i].num=i;

	sort(P+1,P+n+1,paixu);

	for(int i=1;i<=n;i++)	P[i].k=i;

	sort(P+1,P+n+1,huanyuan);

	long long ans=0;

	for(int i=1;i<=n;i++)
	{
		add(P[i].k,1);
		ans+=sum(P[i].k-1);
	}

	printf("%lld",ans%99999997);
}