记录编号	606667	评测结果	AAAAAAAAAA
题目名称	1438.[NOIP 2013]火柴排队	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	0.191 s
提交时间	2025-10-01 17:09:24	内存使用	4.75 MiB

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=1e6+10,mod=99999997;
ll n,ans;
ll a[N],b[N];
ll ar[N],br[N];
ll id[N];
struct tree{
	ll c[N];
	void udate(ll p,ll x){
		for(;p<=n;p+=(p&-p)) c[p]+=x;
		return;
	}
	ll ask(ll p){
		ll ans=0;
		for(;p;p-=(p&-p)) ans+=c[p];
		return ans;
	}
}t;
int main(){
    freopen("MatchNOIP2013.in","r",stdin);
    freopen("MatchNOIP2013.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",ar+i);
        a[i]=ar[i];
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",br+i);
        b[i]=br[i];
    }
    ll l1,l2;
    sort(ar+1,ar+n+1);
    sort(br+1,br+n+1);
    l1=unique(ar+1,ar+n+1)-ar-1;
    l2=unique(br+1,br+n+1)-br-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(ar+1,ar+l1+1,a[i])-ar;
        b[i]=lower_bound(br+1,br+l2+1,b[i])-br;
        id[a[i]]=i;
    }
    /*
    for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	for(int i=1;i<=n;i++) {
		cout<<b[i]<<" ";
	}
	cout<<endl<<endl;
	*/
    for(int i=1;i<=n;i++){
    	a[id[b[i]]]=i;
    	b[i]=i;
	}
	/*
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	for(int i=1;i<=n;i++) {
		cout<<b[i]<<" ";
	}
	*/
	for(int i=1;i<=n;i++){
		t.udate(a[i],1);
		ans+=i-t.ask(a[i]);
		ans%=mod;
	}
	printf("%lld",ans);
    return 0;
}