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

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod=99999997;

struct node{
    int val,id;
}l1[1000100],l2[1000100];

ll n,ans;
ll id1[1000100],f[1000100]; 

bool cmp(node aa,node bb){
    return  aa.val<bb.val;
}

void dg(int l,int r){
    if (l==r) return;
    int mid=(l+r)/2;
    dg(l,mid);
    dg(mid+1,r);
    int l1=l,r1=mid+1,k=l;
    while (l1<=mid && r1<=r){
        if (id1[l1]<=id1[r1]){
            f[k]=id1[l1];
            l1++;k++;
        }else{
            f[k]=id1[r1];
            k++;r1++;
            ans=(ans+mid-l1+1)%mod;
        }
    }
    while (l1<=mid){
        f[k]=id1[l1];
        l1++;k++;
    }
    while (r1<=r){
        f[k]=id1[r1];
        k++;r1++;
    }
    for (int i=l;i<=r;i++){
        id1[i]=f[i];
    }
}


int main(){
//    freopen("in.in","r",stdin);
    freopen("MatchNOIP2013.in","r",stdin);
    freopen("MatchNOIP2013.out","w",stdout);
    scanf("%lld",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&l1[i].val);
        l1[i].id=i;
    }
    for (int i=1;i<=n;i++){
        scanf("%d",&l2[i].val);
        l2[i].id=i;
    }
    sort(l1+1,l1+n+1,cmp);
    sort(l2+1,l2+n+1,cmp);
    for (int i=1;i<=n;i++) id1[l2[i].id]=l1[i].id;
    dg(1,n);
    printf("%lld",ans);
    return 0;
}

/*
4
1 3 4 2
1 7 2 4


1 3 4 2 -> 1 2 3 4 -> 1 4 2 3
1 7 2 4 -> 1 2 4 7 -> 1 3 4 2




*/