记录编号	310327	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]火柴排队	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.181 s
提交时间	2016-09-22 11:09:38	内存使用	1.98 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100003
#define MOD 99999997
int A[MAXN], B[MAXN];
int rkB[MAXN];
int ord[MAXN];
inline bool rankb(int a, int b)
{
    return B[a] < B[b];  
}
int ans = 0;
int tmp[MAXN];
void msort(int l, int m, int r)
{
    int i = l;
    int j = m+1;
    int k = l;
    while(i <= m && j <= r)
    {
        if(ord[i] > ord[j])
        {
            tmp[k++] = ord[j++];
            ans = (ans+m-i+1)%MOD;
        }else
        {
            tmp[k++] = ord[i++];
        }
    }
    while(i <= m)tmp[k++] = ord[i++];
    while(j <= r)tmp[k++] = ord[j++];
    for(int p = l; p <= r; p++)
        ord[p] = tmp[p];
}
void gg(int l, int r)
{
    if(l < r)
    {
        int m = (l+r)>>1;
        gg(l, m);
        gg(m+1, r);
        msort(l, m, r);
    }
}
int main()
{
    freopen("MatchNOIP2013.in", "r", stdin);
    freopen("MatchNOIP2013.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", A+i);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", B+i);
        rkB[i] = i;
    }
    sort(rkB+1, rkB+1+n, rankb);
    for(int i = 1; i <= n; i++)
        ord[i] = rkB[A[i]];
    gg(1, n);
    printf("%d\n", ans);
    return 0;
}