AcWing 107超高速ソート

问题解:実は问题は1つの泡の顺位を言って、しかしきっと直接泡を使うことができなくて...もし解を求めて全部で何回の顺番を交换する必要があるならば、それでは并び合わせのアルゴリズムを使って、直接逆顺番の対を计算することができます.ACコード:

#include
#include
#include
#include
#include

#define ll long long

using namespace std;

const int maxn = 5e5 + 17;

ll a[maxn] = {
     },b[maxn] = {
     },cnt = 0;

void merge_sort(int l,int r)
{
     
    if(l >= r)return ;
	int mid = (l + r)/2;
	int p = l;
	int q = mid + 1;
	int pos = l;
	merge_sort(l,mid);
	merge_sort(mid + 1,r);
	while(p <= mid||q <= r){
     
		if(q > r||(p <= mid&&a[p] <= a[q])){
     
			b[pos++] = a[p++];
		}
		else{
     
			cnt += mid - p + 1;
			b[pos++] = a[q++];
		}
	}
	for(int i = l;i <= r;i++){
     
		a[i] = b[i];
	}
}

int main()
{
     
    int n;
    while(scanf("%d",&n)){
     
        cnt = 0;
        if(n == 0) break;
        for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
        merge_sort(1,n);
        printf("%lld
",cnt);
    }
    return 0;
}