10分,求调
查看原帖
10分,求调
655485
eifiwohie楼主2024/8/20 19:17
#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[1000005];
int lb(int x){
	return x&-x;
}
int n;
const int mod=99999997;
struct node{
	int rk;
	int val;
	int id;
};
int tot;
node numa[100005];
node numb[100005];
node numbb[100005];
bool cmp(node a,node b){
	return a.val<b.val;
}
bool cmp1(node a,node b){
	return a.val>b.val;
}
bool cmp2(node a,node b){
	return a.id<b.id;
}
void modify(int x,int k){
	while(x<=n){
		c[x]+=k;
		x+=lb(x);
	}
}
int query(int x){
	int ans=0;
	while(x>0){
		ans+=c[x];
		x-=lb(x);
	}
	return ans;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>numa[i].val;
		numa[i].id=i;
	}
	
	for(int i=1;i<=n;i++){
		cin>>numb[i].val;
	}
	sort(numa+1,numa+1+n,cmp);
	for(int i=1;i<=n;i++){
		numa[i].rk=++tot;
//		if(numa[i].val!=numa[i+1].val)tot++; 
	}
	for(int i=1;i<=n;i++){
		numbb[numa[i].rk]=numb[numa[i].id];
		numbb[i].id=i;
	}
	sort(numbb+1,numbb+1+n,cmp1);
	tot=1;
	for(int i=1;i<=n;i++){
		numbb[i].rk=tot;
		if(numbb[i].val!=numbb[i+1].val)tot++;
	}
	sort(numbb+1,numbb+1+n,cmp2);
//	for(int i=1;i<=n;i++){
//		cout<<numbb[i].rk<<" ";
//	}
	//接下来求逆序对 
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=query(numbb[i].rk-1);
		ans%=mod;
		modify(numbb[i].rk,1);
	}
	
	cout<<ans%mod<<endl;
	return 0;
}
2024/8/20 19:17
加载中...