记录编号	606668	评测结果	AAAAAAAAAA
题目名称	1438.[NOIP 2013]火柴排队	最终得分	100
用户昵称	xxz	是否通过	通过
代码语言	C++	运行时间	0.169 s
提交时间	2025-10-01 17:09:32	内存使用	4.23 MiB

#include<bits/stdc++.h>
#define mod 99999997 
using namespace std;
int n,a[1234567],b[1234567],c[1234567],d[1234567],e[1234567],t[1234567],tree[1234567],ans;
int lowbit(int x){
	return x&(-x);
}
int ask(int x){
	int ans=0;
	for(;x;x-=lowbit(x)){
		ans+=tree[x];
	}
	return ans;
}
void add(int x,int y){
	for(;x<=n;x+=lowbit(x))tree[x]+=y;
}
void lsh(int x[],int y[]){
	for(int i=1;i<=n;i++){
		t[i]=x[i];
	}
	sort(t+1,t+n+1);
	for(int i=1;i<=n;i++){
		y[i]=lower_bound(t+1,t+n+1,x[i])-t;
	}
}
int main(){
	freopen("MatchNOIP2013.in","r",stdin);freopen("MatchNOIP2013.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	lsh(a,c);
	lsh(b,d);
	for(int i=1;i<=n;i++){
		e[d[i]]=i;
	}
	for(int i=1;i<=n;i++){
		c[i]=e[c[i]];
	}
	for(int i=n;i>=1;i--){
		ans+=ask(c[i]-1)%mod;
		ans%=mod;;
		add(c[i],1);
	}
	cout<<ans%mod;
	return 0;
}