发布题解P8613

lunivia · 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 );
}

难度建议评定：绿/蓝。