luogu 1966 火柴排队 离散化+逆序对

时间：2023-12-04 13:28:26

题意：找到最小改变对数使a数组的第i大和b数组的第i大相等

则先将a,b,数组编号再排序，则数组显示的就是排名第i的数的编号

再关键一步：c[a[i].id]=b[i].id

实质上就是新建一个数组，按照现有a数组的排布，和b数组进行比较，看是否有逆序对存在，有则需要更换，故再求逆序对即可

#include<bits/stdc++.h>

#define rep(i,x,y) for(register int i=x;i<=y;i++)

#define dec(i,x,y) for(register int i=x;i>=y;i--)

#define LL long long

#define int long long

using namespace std;

const int mod=;

const int N=2e6+;

inline int read(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;}int n,ans,c[N],k[N];

pair<int,int> a[N],b[N];

inline void add(int x,int d){for(int i=x;i<=n;i+=i&(-i)) k[i]+=d;}

inline int query(int x){int ans=;for(int i=x;i;i-=i&(-i)) ans+=k[i];return ans;}

signed main(){

    n=read();

    rep(i,,n) a[i].first=read(),a[i].second=i;

    rep(i,,n) b[i].first=read(),b[i].second=i;

    sort(a+,a++n);sort(b+,b++n);

    rep(i,,n) c[a[i].second]=b[i].second;

    dec(i,n,) ans=(ans+query(c[i]))%mod,add(c[i],);

    printf("%lld\n",ans%mod);return ;

}

相关文章