记录编号	194376	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.188 s
提交时间	2015-10-16 16:06:30	内存使用	5.66 MiB

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const long long MAXN(100010), MOD(99999997);
long long n,a[MAXN],b[MAXN],aa[MAXN],bb[MAXN],wh[MAXN]={0},ans=0,t[MAXN],where,
whe[MAXN]={0};
void merge(long long, long long);
ifstream fin("MatchNOIP2013.in");
ofstream fout("MatchNOIP2013.out");
#define cin fin
#define cout fout

main()
{
	cin >> n;
	for (long long i = 1; i <= n; ++i){
		cin >> a[i];
		aa[i] = a[i];
	}
	for (long long i = 1; i <= n; ++i){
		cin >> b[i];
		bb[i] = b[i];
	}
	fin.close();
	
	sort(aa + 1, aa + n + 1);
	for (long long i = 1; i <= n; ++i){
		where = lower_bound(aa + 1, aa + n + 1, a[i]) - aa;
//		cout << i << ' ' << where << ' ' << a[i] << ' ' << aa[i] << endl;
		wh[where] = i;	//第where小的数排第i个 
	}
	sort(bb + 1, bb + n + 1);
	for (long long i = 1; i <= n; ++i){
		where = lower_bound(bb + 1, bb + n + 1, b[i]) - bb;
		whe[i] = wh[where];
//		cout << whe[i] << ' ';
	}
//	cout << endl;
	merge(1, n);
	
	cout << (ans + MOD) % MOD;
	fout.close();
//	for (; ; ); 
}

void merge(long long l, long long r)	//闭区间，对whe数组从小到大归并排序。 
{
	if (l >= r)
		return;
	long long mid = (l + r) >> 1, i = l, j = mid + 1, p = l;
	merge(l, mid);
	merge(mid + 1, r);
	while (i <= mid && j <= r)
		if (whe[i] <= whe[j])
			t[p++] = whe[i++];
		else{
			t[p++] = whe[j++];
			ans = (ans + mid - i + 1) % MOD;
		}
	while (i <= mid)
		t[p++] = whe[i++];
	while (j <= r)
		t[p++] = whe[j++];
	for (i = l; i <= r; ++i)
		whe[i] = t[i];
}