求调(回复必关注)
查看原帖
求调(回复必关注)
305735
Jean_Gunnhildr楼主2024/8/30 10:16
#include<bits/stdc++.h>
using namespace std;
int n,m,c[200005],pos[500005],a[200005];
inline int lowbit(int x){
	return x&(-x); 
}
inline void update(int pos,int num){//更新 
	for(int i=pos;i<=n+m;i+=lowbit(i)) c[i]+=num;
}
inline bool cmp(int t1,int t2){
	return t1>t2;
}
inline int sum(int x){
	int temp=0;
	for(int i=x;i>=1;i-=lowbit(i)) temp+=c[i];
	return temp;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[n-i+1];
		pos[a[n-i+1]]=n-i+1;//记录位置 
		update(n-i+1,1);
	}
	for(int i=1;i<=m;i++){
		cin>>a[n+i];
		pos[a[n+i]]=n+i;
		update(n+i,1);
	}
	sort(a+1,a+1+n+m,cmp);
	int last=n;
	long long ans=0;
	for(int i=1;i<=n+m;i++){
		if(last>pos[a[i]]){
			ans=ans+sum(last)-sum(pos[a[i]]);
			update(pos[a[i]],-1);
			last=pos[a[i]];
		}
		else{
			ans=ans+sum(pos[a[i]]-1)-sum(last);
			update(pos[a[i]],-1);
			last=pos[a[i]];
		}
	}
	cout<<ans<<endl;
	return 0;
}

测评记录

2024/8/30 10:16
加载中...