超快速排序

title: 超快速排序
date: 2024-01-05 11:51:43
tags: 逆序对
categories: 算法进阶指南

题目大意

解题思路

逆序数是一个序列每一个数的左边有多少比他本身大的值。将一个序列排序完整，最小交换次数即是逆序数之和。使用归并排序的同时，将每一个逆序数求出并相加。

代码实现

#include<iostream>
#include<string.h>
#include<cstring>
#include<unordered_map>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#define int long long

#define bpt __builtin_popcountll

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 2E6 + 10, mod = 998244353;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

const int MOD = 998244353;

priority_queue<int, vector<int>>l;//大根堆
priority_queue<int, vector<int>, greater<int>> r;//小根堆

int a[N], b[N];
int cnt = 0;
int n;


void merge(int l,int r,int *a)
{
	if (l >= r) return;
	int mid = l + r >> 1;
	merge(l, mid, a);
	merge(mid + 1, r, a);

	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++) {
		if (i <= mid && a[i] <= a[j] || j > r) {
			b[k] = a[i++];
		}
		else {
			cnt += mid - i + 1;
			b[k] = a[j++];
		}
	}

	for (int k = l; k <= r; k++) {
		a[k] = b[k];
	}
}
signed main()
{
	while (cin >> n && n) {
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}

		cnt = 0;
		merge(1,n,a);
		cout << cnt << endl;
	
	}

}