Inverse Pair
题目传送门：
题面：
题目大意：
给定一个无重复的排列，每个元素可以执行+1的操作或不变，求操作后最少的逆序对对数。
思路：
思考怎么加可以减少逆序对对数，如果x 在 x+1 的后面, 则可以通过操作让逆序对减少。
而且因为是排列，所以不会增加逆序对（+1也最多变得和某个数一样，不会再变大了）。
但是可能后续操作会覆盖之前消除的记录。
如题解。
但实际上也没那么复杂，遇到如果x 在 x+1 的后面,直接全部暴力让x+1，最后再跑一遍看有几个逆序对。
merge_sort求逆序数对的方法《挑程》上有。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
int q[maxn], tmp[maxn];
int vis[maxn] = {0};
//ll merge_sort(int l, int r) {
// if (l >= r) return 0;
// //区间没有元素返回
// int mid = l + r >> 1;
// ll ans = merge_sort(l, mid) + merge_sort(mid + 1, r);
// int cnt = 0;
// int i = l;
// int j = mid + 1;
// while (j <= r && i <= mid) {
// if (q[i] <= q[j])
// tmp[cnt++] = q[i++];
// else {
// ans += mid - i + 1;
// tmp[cnt++] = q[j++];
// }
// }
// while (j <= r) tmp[cnt++] = q[j++];
// while (i <= mid) tmp[cnt++] = q[i++];
// for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
// return ans;
//}
ll merge_sort(int l, int r) {
if (l >= r)
return 0;
int mid = l + r >> 1;
ll ans = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (q[i] <= q[j])
tmp[k++] = q[i++];
else
tmp[k++] = q[j++], ans += (ll) mid - i + 1;
while (i <= mid)
tmp[k] = q[i], k++, i++;
while (j <= r)
tmp[k] = q[j], k++, j++;
for (int i = l, j = 0; i <= r; j++, i++)
q[i] = tmp[j];
return ans;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> q[i];
for (int i = 1; i <= n; i++) {
if (vis[q[i] + 1])q[i]++;
else vis[q[i]] = 1;
}
cout << merge_sort(1, n) << endl;
return 0;
}