#include <bits/stdc++.h>
using namespace std;
// ================= 代码实现开始 =================
/* 请在这里定义你需要的全局变量 */
long long cnt;
vector<int> seq;
vector<int> seqtmp;
// 这个函数的功能是计算答案（即最少花费的金钱）
// n：表示序列长度
// a：存储整个序列 a
// 返回值：最少花费的金钱（需要注意，返回值的类型为 64 位有符号整数）
void mergeSort(int l,int r)
{
if(l == r)
return;
int mid = (l+r) >> 1;
mergeSort( l , mid );
mergeSort(mid + 1,r);
int p = l;
int q = mid + 1;
for(int i=l; i<=r; i++)
{
if(seq[p] <= seq[q] && p<=mid || q > r)
//p<=mid可以进行前半序列插入
//q > r同理
seqtmp[i] = seq[p++];
else
{
seqtmp[i] = seq[q++];
cnt = cnt + mid + 1 - p;
}
}
for(int i=l; i<=r; i++)
{
seq[i] = seqtmp[i];
}
}
long long getAnswer(int n, vector<int> a)
{
seq = a;
seqtmp.resize(n);
cnt = 0;
mergeSort(0,n-1);
return cnt;
}
// ================= 代码实现结束 =================
int main()
{
int n, tmp;
vector<int> a;
a.clear();
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &tmp);
a.push_back(tmp);
}
long long ans = getAnswer(n, a);
cout << ans << '\n';
return 0;
}
当进行TwoWayMerge的时候，如果右边的数组插入左边的数组，如果右边
seq[p] > seq[q]
则 情况类似于 1 9 10
5 6 7
插入到
1 5
此时逆序对有（5,9） （5,10）
为前半序列未插入时候的空位，因为空位的数量就是5 小于前列未插入数的数目，所以为
int cnt = 0;
cnt = cnt +mid + 1 - p;
当前半序列都插满的时候
1 5 6 7
mid + 1 - p 就是前半序列未插入的数量 每次后半序列插入都和前半序列未插入的数构成逆序对。
