开辟无人区

逆序对

解题思路： 1.根据题目可以知道，我们要让所有上下对应的两根火柴差值的平方最小。如果让两列火柴分别从小到大排序，那么我们就可以求出最小时的值。 证明：设两列两递增元素的数据a1 a2 b1 b2,那么(a1-b1)^2 + (a2-b2)^2 = a1^2 + b1^2 - 2a1b1 + a2^2 + b2^2 - 2a2b2 (a1-b2)^2 + (a2-b1)^2 = a1^2 + b2^2 - 2a1b2 + a2^2 + b1^2 - 2a2b1 比较-2(a1b1+a2b2)与-2(a1b2+a2b1)大小 作差=>>a1b2+a2b1-a1b1-a2b2 = b1(a2-a1)+b2(a1-a2) = (a1-a2)(b2-b1)<0故顺序排列时平方差的和最小。 2.离散化：为了简化数据、方便计算，我们可以给数据编号（具体见代码） 3.当排列完成后可以找到上下两组数列的一一对应的关系。再根据这个关系进行排列。

#include
using namespace std;
#define LL long long
const int N=100000,M=99999997;
LL n,A1[N][2],A2[N][2],A3[N][2],sum=0;
void mergesort(LL a[][2],int low,int hight);
void merge(LL a[][2],int low, int mid, int hight);
void merge2(LL a[][2],int low, int mid, int hight);
void merge2(LL a[][2],int low, int mid, int hight){
	const int nn = hight - low + 1;
	LL* b = new LL[nn];
	int i=low,j=mid+1,k=0;
	while(i<=mid && j<=hight){
		if(a[i][1]<=a[j][1]){
			b[k++] = a[i++][1];
		}
		else{
			b[k++] = a[j++][1];
			sum += mid-i+1;
		}
	}
	while(i<=mid) b[k++] = a[i++][1];
	while(j<=hight) b[k++] = a[j++][1];
	k=0;
	for(int i=low;i<=hight;i++) a[i][1] = b[k++];
	delete []b;
}
void merge(LL a[][2],int low, int mid, int hight){
	const int nn = hight - low + 1;
	LL* b = new LL[nn];
	LL* c = new LL[nn];
	int i=low,j=mid+1,k=0;
	while(i<=mid && j<=hight){
		if(a[i][0]<=a[j][0]){
			b[k++] = a[i++][0];
			c[k-1] = a[i-1][1];
		}
		else{
			b[k++] = a[j++][0];
			c[k-1] = a[j-1][1];
		}
	}
	while(i<=mid){
		b[k++] = a[i++][0];
		c[k-1] = a[i-1][1];
	}
	while(j<=hight){
		b[k++] = a[j++][0];
		c[k-1] = a[j-1][1];
	}
	k=0;
	for(int i=low; i<= hight; i++){
		a[i][0] = b[k++];
		a[i][1] = c[k-1];
	}
	delete []b;
	delete []c;
}
void mergesort(LL a[][2],int low,int hight,int le){
	if(!le){
		if(low < hight){
			int mid = (hight + low)/2;
			mergesort(a,low,mid,0);
			mergesort(a,mid+1,hight,0);
			merge(a,low,mid,hight);
		}
	}
	else{
		if(low < hight){
			int mid = (hight + low)/2;
			mergesort(a,low,mid,1);
			mergesort(a,mid+1,hight,1);
			merge2(a,low,mid,hight);
		}
	}
}
int main(){
	scanf("%lld",&n);
	for(int i=0;i<n;i++){        
		scanf("%lld",&A1[i][0]);
		A1[i][1] = i;           //数据离散化 
	}
	for(int i=0;i<n;i++){
		scanf("%lld",&A2[i][0]);
		A2[i][1] = i;           //数据离散化 
	}
	mergesort(A1,0,n-1,0);
	mergesort(A2,0,n-1,0);
	for(int i=0;i<n;i++){       //找到一一对应的关系 
		A3[i][0] = A1[i][1];
		A3[i][1] = A2[i][1];
	}
	mergesort(A3,0,n-1,0);
	mergesort(A3,0,n-1,1);      //实际就是求逆序对数 
	printf("%lld",sum%M);
	return 0;
}