自动搬运

查看原文

来自洛谷，原作者为

	ZVitality The end.

搬运于2025-08-24 22:40:42，当前版本为作者最后更新于2022-10-26 08:37:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

貌似本来用树状数组做，但是归并也能求。

题目看完后首先想到的应该是冒泡排序，每次直接枚举交换两个相邻的数，然后就可以求解，时间复杂度为 $O(n^2)$。由于 $n\le10^{5}$，不可行。

考虑像分治求逆序对的想法，能否根据两块的结果求出来一个大的结果？显然是可以的，它们之间的距离为 $l-r+1$，那我们就可以像在求逆序对一样，一边分治，一边求答案。

时间复杂度为 $O(n \log n)$，能够稳稳地过。

由于结论很短，我就给点代码理解吧。

void Merge( Point *a , int first , int end ) { //归并排序
	int tmp = first , mid = first + end >> 1 , p = first , q = mid + 1;
	while( p <= mid && q <= end ) 
		if( a[ p ].h > a[ q ].h ) {
			a[ q ].t += mid + 1 - p; //记录答案
			c[ tmp++ ] = a[ q++ ];
		}
		else {
			a[ p ].t += q - 1 - mid; //记录答案
			c[ tmp++ ] = a[ p++ ];
		}
	while( q <= end ) c[ tmp++ ] = a[ q++ ];
	q--;
	while( p <= mid ) a[ p ].t += q - mid , c[ tmp++ ] = a[ p++ ];
	for( int i = first ; i <= end ; i++ ) a[ i ] = c[ i ];
}

void MergeSort( Point *a , int first , int end ) {//分治主程序
	if( first == end ) return;
	int mid = first + end >> 1;
	MergeSort( a , first , mid ) , MergeSort( a , mid + 1 , end );
	Merge( a , first , end );
}

难度建议评定：绿/蓝。