10pts 求条
查看原帖
10pts 求条
935574
dulinfan2023楼主2025/1/19 23:13
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() cout<<"come on"<<'\n'
const int mod=1e8-3;
struct edge{
	int x,id;
}a[100005],b[100005],aa[100005];
map<int,int> mp;
bool cmp(edge a,edge b){ return a.x!=b.x?a.x<b.x:a.id<b.id; }
bool cmp2(edge a,edge b){ return a.x!=b.x?a.x>b.x:a.id>b.id; }
int ans,tree[100005],n;
int l(int u){ return (u)&(-u); }
void add(int x,int p){ for(;x<=n;x+=l(x))tree[x]+=p; }
int query(int x){
	int res=0;
	for(;x>0;x-=l(x))res+=tree[x];
	return res;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x,a[i].id=i;
	for(int i=1;i<=n;i++)cin>>b[i].x,b[i].id=i;
	sort(a+1,a+1+n,cmp),sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++){
		mp[b[i].id]=i;
	}
	for(int i=1;i<=n;i++){
		aa[i].x=mp[a[i].id];
		aa[i].id=i;
	}
	sort(aa+1,aa+1+n,cmp2);
	for(int i=1;i<=n;i++){
		add(aa[i].id,1);
		ans+=query(aa[i].id-1);
	}
	cout<<ans;
	return 0;
}
2025/1/19 23:13
加载中...