求调
查看原帖
求调
1269423
huge_wave楼主2024/11/3 08:23
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
#define int long long
struct noid{
	int a,b;
}g[N];
int aa[N];
int bb[N];
bool cmp(const noid&x,const noid&y){
	if(x.b==y.b){
		return x.a<y.a;
	}
	return x.b<y.b;
}
int ans=0;
void sort1(int l,int r){
	if(l==r){
		return ;
	}
	int mid=(l+r)>>1;
	sort1(l,mid);
	sort1(mid+1,r);
	int k=l;
	for(int ax=l,bx=mid+1;bx<=r||ax<=mid;){
		if(bx>r||(g[ax].a<=g[bx].a&&ax<=mid)){
			aa[k]=g[ax].a;
			ax++;
			k++;
		}
		else{
			aa[k]=g[bx].a;	
			k++;
			bx++;
			ans+=mid-ax+1;
		}
	}
	for(int i=l;i<=r;i++){
		g[i].a=aa[i];
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>g[i].a;
		bb[i]=g[i].a;
	}
	for(int i=1;i<=n;i++){
		cin>>g[i].b;
		
	}
	sort(g+1,g+1+n,cmp);
	sort(bb+1,bb+1+n);
	sort1(1,n);
	cout<<ans;
	return 0;
}
2024/11/3 08:23
加载中...