比赛 20251001国庆欢乐赛1 评测结果 AAAAAAAAWW
题目名称 火柴排队 最终得分 80
用户昵称 秋_Water 运行时间 0.251 s
代码语言 C++ 内存使用 4.61 MiB
提交时间 2025-10-01 11:10:58
显示代码纯文本
#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]+=val;
    }
}
int query(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i)){
        ans+=t[i];
    }
    return ans;
}
signed main(){
    freopen("MatchNOIP2013.in","r",stdin);
    freopen("MatchNOIP2013.out","w",stdout);
    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;
    
    return 0;
}