外贸网站域名能用cn做后缀吗,宠物主题网站模板,芜湖做网站哪个公司好,网络自助服务平台title: 超快速排序 date: 2024-01-05 11:51:43 tags: 逆序对 categories: 算法进阶指南
题目大意 解题思路 逆序数是一个序列每一个数的左边有多少比他本身大的值。将一个序列排序完整#xff0c;最小交换次数即是逆序数之和。使用归并排序的同时#xff0c;将每一个逆序数求…
title: 超快速排序 date: 2024-01-05 11:51:43 tags: 逆序对 categories: 算法进阶指南
题目大意 解题思路 逆序数是一个序列每一个数的左边有多少比他本身大的值。将一个序列排序完整最小交换次数即是逆序数之和。使用归并排序的同时将每一个逆序数求出并相加。 代码实现
#includeiostream
#includestring.h
#includecstring
#includeunordered_map
#includeiomanip
#includevector
#includealgorithm
#includemath.h
#includequeue
#define int long long#define bpt __builtin_popcountllusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, 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_queueint, vectorintl;//大根堆
priority_queueint, vectorint, greaterint 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;}}
