Why Did the Cow Cross the Road (P)

Why Did the Cow Cross the Road (P)

思路

映射$+$逆序对

考虑用先映射，然后用$BIT$一次求出逆序对数，然后模拟移动最后一个的变化。

注意左右不等价，都要移动$n$次。

时间复杂度：$O(nlogn)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define lowbit(x) x&(-x)
int mp[N],a[N],b[N];
ll tr[N];
int n;
void upd(int x,ll k){
    while(x<=n){
        tr[x]+=k;
        x+=lowbit(x);
    }
}
ll que(int x){ll s=0;
    while(x){
        s+=tr[x];
        x-=lowbit(x);
    }return s;
}
ll ans=1e18;
int c[N],d[N];
void solve(int *a,int *b){
    mst(tr,0);
    memcpy(c+1,a+1,(n+1)*sizeof(int));memcpy(d+1,b+1,(n+1)*sizeof(int));
    ll res=0;
    for(int i=1;i<=n;i++) mp[c[i]]=i;
    for(int i=1;i<=n;i++){
        d[i]=mp[d[i]];
        res+=que(n)-que(d[i]);
        upd(d[i],1LL);
    }
    ll tmp=res;
    for(int i=n;i>=0;i--){
        //printf("res=%lld\n",res);
        res+=2*d[i]-n-1;
        tmp=min(tmp,res);
    }
    ans=min(ans,tmp);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    solve(a,b);
    solve(b,a);
    printf("%lld\n",ans);
    return 0;
}