80分求助
查看原帖
80分求助
641064
mengxiang2010楼主2024/1/26 09:48
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,ans,a[N],b[N],c[N],d[N],e[N],f[N],g[N],h[N];
int lowbit(int x){
	return x&-x;
}
int getsum(int x){
	int ans=0;
	while(x>0){
		ans+=h[x];
		x-=lowbit(x);
	}
	return ans;
}
void add(int x,int k){
	while(x<=n){
		h[x]+=k;
		x+=lowbit(x);
	}
}
bool cmp1(int x,int y){
	return a[x]<a[y];
}
bool cmp2(int x,int y){
	return b[x]<b[y]; 
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		d[i]=i;
	}
	stable_sort(c+1,c+n+1,cmp1);
	stable_sort(d+1,d+n+1,cmp2);
	for(int i=1;i<=n;i++){
		a[c[i]]=i;
		b[d[i]]=i;
	}
	for(int i=1;i<=n;i++){
		f[b[i]]=i;
	}
	for(int i=1;i<=n;i++){
		g[i]=f[a[i]];
	}
	for(int i=n;i>=1;i--){
		ans+=getsum(g[i]-1);
		add(g[i],1);
	}
	cout<<ans;
	return 0;
}
2024/1/26 09:48
加载中...