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

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010;
const int mod =  99999997; 
struct node{
	int v,idx;
}a[N],b[N],c[N];

bool cmp(node a,node b){
	return a.v<b.v;
}

bool cmp1(node a,node b){
	if(a.v==b.v)return a.idx>b.idx;
	return a.v>b.v; 
}

int sum[N];
int n,res;

int lowbit(int x){
	return x&(-x);
} 

void add(int x,int v){
	for(int i=x;i<=n;i+=lowbit(i))sum[i]+=v;
}

int query(int x){
	int cnt=0;
	for(int i=x;i;i-=lowbit(i))cnt+=sum[i];
	return cnt;
}


signed main(){
	freopen("MatchNOIP2013.in","r",stdin);
	freopen("MatchNOIP2013.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i].v);
		a[i].idx=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i].v);
		b[i].idx=i;
	}
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++){
		c[b[i].idx].v=a[i].idx;
		c[i].idx=i;
	}
	sort(c+1,c+1+n,cmp1);
	for(int i=1;i<=n;i++){
		res=(res+query(c[i].idx)%mod)%mod;
//		res+=query(c[i].idx);
		add(c[i].idx,1);
	}
	printf("%lld",res);
	return 0;
}