记录编号	606649	评测结果	AAAAAAAAAA
题目名称	1438.[NOIP 2013]火柴排队	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.143 s
提交时间	2025-10-01 16:33:22	内存使用	4.25 MiB

#include<bits/stdc++.h>
using namespace std;
const int mod=99999997;
long long n,d[10000005],f[1000005],ans=0;
struct node{
    int o,p;
}a[1000005],b[1000005];
bool cmp(node x,node y){
    return x.o<y.o;
}
void gb(int s,int t){
    if(s==t) return;
    int mid=(s+t)/2;
    gb(s,mid);
    gb(mid+1,t);
    int i=s,k=s,j=mid+1;
    while(i<=mid&&j<=t){
        if(d[i]<=d[j]){
            f[k]=d[i];
            ++k;
            ++i;
        }
        else{
            f[k]=d[j];
            ++k;
            ++j;
            ans=(ans+mid-i+1)%mod;
        }
    }
    while(i<=mid){
        f[k]=d[i];
        ++k;
        ++i;
    }
    while(j<=t){
        f[k]=d[j];
        ++k;
        ++j;
    }
    for(int i=s;i<=t;i++){
        d[i]=f[i];
    }
}
int main(){
	freopen("MatchNOIP2013.in","r",stdin);
	freopen("MatchNOIP2013.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i].o;
    	a[i].p=i;
    }
    for(int i=1;i<=n;i++){
    	cin>>b[i].o;
    	b[i].p=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
    	d[b[i].p]=a[i].p;
    } 
    gb(1,n);
	cout<<ans<<"\n";
    return 0;
}