记录编号	195510	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.065 s
提交时间	2015-10-19 06:57:56	内存使用	3.34 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define lowbit(x) (x&-x)
#define P 99999997
using namespace std;

struct Node{
	int k, id;
	bool operator < (Node t) const
	{
		return k < t.k;
	}
};

int n, ans, f[100005], sota[100005], sotb[100005], pos[100005];
Node a[100005], b[100005];

void get(int &x)
{
	char c = getchar(); x = 0;
	while(c < '0' || c > '9') c = getchar();
	while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}

void add(int x)
{
	while(x <= n) f[x] ++, x += lowbit(x);
}
int sum(int x)
{
	int res = 0;
	while(x) res += f[x], x -= lowbit(x);
	return res;
}

int main()
{
	freopen("MatchNOIP2013.in","r",stdin);
	freopen("MatchNOIP2013.out","w",stdout);
	
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) a[i].id = b[i].id = i;
	for(int i = 1; i <= n; i++)	get(a[i].k);
	for(int i = 1; i <= n; i++)	get(b[i].k);

	sort(a+1, a+n+1);
	sort(b+1, b+n+1);
	
	for(int i = 1; i <= n; i++) sota[a[i].id] = i;
	for(int i = 1; i <= n; i++) sotb[b[i].id] = i;
	
	for(int i = 1; i <= n; i++) pos[sota[i]] = i;
	for(int i = 1; i <= n; i++) sotb[i] = pos[sotb[i]];
	
	for(int i = n; i; i--) 
	{
		ans = (ans + sum(sotb[i]-1)) % P;
		add(sotb[i]);
	}
	printf("%d", ans);
	return 0;
}