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

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) x&-x
const int N=1e6+7;
int n,t[N],c[N];
struct node{
    int val,id;
}a[N],b[N];
bool cmp(node x,node y){
    return x.val<y.val;
}
void add(int x,int val){
    for(int i=x;i<=n;i+=lowbit(i)){
        t[i]=(t[i]+val)%99999997;
    }
}
int query(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i)){
        ans=(ans+t[i])%99999997;
    }
    return ans;
}
signed main(){;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].val;
        a[i].id=i;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i].val;
        b[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
        c[b[i].id]=a[i].id;
    }
    int ans=0;
    for(int i=n;i;i--){
        ans+=query(c[i]);
        add(c[i],1); 
    }
    cout<<ans%99999997;
    
    return 0;
}