蒟蒻0分求助
查看原帖
蒟蒻0分求助
950927
_luo_gu楼主2023/11/4 19:39
#include <bits/stdc++.h>
#define int long long
using namespace std ;
struct person{
	int val ;
	int ii ;
	int otval ;
};
person a[100005] , b[100005] ;
bool cmp1( person a , person b ){
	return a.val < b.val ;
}
bool cmp2(person a , person b ){
	return a.ii < b.ii ;
}
bool cmp3(person a , person b ){
	return a.otval < b.otval ;
}
int lowbit(int x ){
	return x &(-x) ;
} 
int n , c[100005] , cnt ;
signed main(){
	scanf("%lld" , &n );
	for( int i = 1 ; i <= n ; i ++ ){
		scanf("%lld" , &a[i].val );
		a[i].ii = i ;
	}
	for( int i = 1 ; i <= n ; i ++ ){
		scanf("%lld" , &b[i].val );
		b[i].ii = i ;
	}
	stable_sort(a+1 , a+n+1 , cmp1 );
	stable_sort(b+1 , b+n+1 , cmp1 );
	for( int i = 1 ; i <= n ; i ++ ){
		a[i].val = b[i].val = i ;
		a[i].otval = b[i].val ;
		b[i].otval = a[i].val ;
	}
	stable_sort(b+1 , b+n+1 , cmp3 );
	//a按照升序排列,b按照与a的配对排列 
	cnt = 0 ;
	for( int i = n ; i >= 1 ; i -- ){
		int j = a[i].val ;
		while( j < n ){
			c[j] ++ ;
			j += lowbit(j) ;
		}
		j = a[i].ii - 1 ;
		int num = 0 ;
		while( j > 0 ){
			num += c[j] ;
			j -= lowbit(j) ;
		}
		cnt += num ;
	}
	printf("%lld" , cnt );
	return 0 ;
}

感谢大佬!好人一生平安!

2023/11/4 19:39
加载中...