比赛 20251001国庆欢乐赛1 评测结果 AAAAAAAAAA
题目名称 火柴排队 最终得分 100
用户昵称 郑霁桓 运行时间 0.165 s
代码语言 C++ 内存使用 4.56 MiB
提交时间 2025-10-01 10:54:23
显示代码纯文本
#include<bits/stdc++.h> 
using namespace std;
long long n,tr[100005],c[100005],as,p,t[100005],pp[100005],M=99999997;
struct nm{
    long long v,id;
}b[100005],a[100005];
void ad(long long x){
    for(;x<=n;x+=x&(-x)) tr[x]++;
}
long long sm(long long x){
    long long ss=0;
    for(;x;x-=x&(-x)) ss+=tr[x];
    return ss;
}
bool cc(nm x,nm y){
    return x.v<y.v;
}
bool ccc(nm x,nm y){
    return x.id<y.id;
} 
int main(){
    freopen("MatchNOIP2013.in","r",stdin);
    freopen("MatchNOIP2013.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].v,a[i].id=i;
    sort(a+1,a+n+1,cc);
    for(int i=1;i<=n;i++) cin>>b[i].v,b[i].id=i,pp[i]=b[i].v;
    sort(pp+1,pp+n+1);
    for(int i=1;i<=n;i++) b[i].v=a[lower_bound(pp+1,pp+n+1,b[i].v)-pp].id;
    sort(b+1,b+n+1,ccc);
    for(int i=1;i<=n;i++){
        as+=i-sm(b[i].v)-1,as%=M;
        ad(b[i].v);
    }
    cout<<as%M;
    return 0;
}