比赛 20251001国庆欢乐赛1 评测结果 AAAAAAAAAA
题目名称 火柴排队 最终得分 100
用户昵称 zhyn 运行时间 0.149 s
代码语言 C++ 内存使用 4.65 MiB
提交时间 2025-10-01 09:59:58
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define maxn 200005

int n;

struct node{
    ll x;
    int y;
};

node a[maxn],b[maxn];
ll ans=0;
int t[maxn];
int u[maxn],v[maxn],r[maxn],last[maxn];

bool cmp(node p,node q){
    return p.x<q.x;
}
const ll mod=99999997;


void meg(int l,int r){
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	meg(l,mid),meg(mid+1,r);
	for(int i=l,j=mid+1,k=l;k<=r;k++){
		if(i==mid+1){
			t[k]=last[j++];
		}
		else if(j==r+1){
			t[k]=last[i++];
		}
		else{
			if(last[i]<=last[j]){
				t[k]=last[i++];
			}
			else{
				t[k]=last[j++];
				ans+=mid-i+1;
				ans%=mod;
			}
		}
	}
	for(int i=l;i<=r;i++){
		last[i]=t[i];
	}
}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    
    freopen("MatchNOIP2013.in","r",stdin);
    freopen("MatchNOIP2013.out","w",stdout);
    
    cin>>n;
    
    
    for(int i=1;i<=n;i++){
        cin>>a[i].x;
        a[i].y=i;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i].x;
        b[i].y=i;
    }      
    
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n,cmp);
    
    for(int i=1;i<=n;i++){
        u[a[i].y]=i;
        v[b[i].y]=i;
    }
    
    for(int i=1;i<=n;i++){
        r[u[i]]=i;
    }
    
    for(int i=1;i<=n;i++){
        last[i]=r[v[i]];
    }
    
    meg(1,n);
    cout<<ans;
    
    
    
    
    return 0;
}