I题（Inverse Pair）

这题看了好一会儿才发现是逆序对，没想到题目就明写了是逆序对：D
链接

题目描述：
对于序列 t（1…n），我们定义它的权重是成对的（i，j）满足 i<j 和 ti>tj
现在给定一个序列 a（1…n），你需要选择一个序列b（1…n）满足 bi属于{0，1}使序列的权重最小化
c（1…n）满足 ci = ai + bi
第一行输入 n
第二行输入 n 个数
我们保证 ai 是{1，2…n}
输出 c（1…n）中最小的权重

题意：给一个数组，我们可以选择数组中任意多的数字加一，使得该数组的逆序数最小。

题解：
若数字 X 前存在 X + 1 我们把这个数加一，若不存在则将该数字标记为存在
我们可以使用 hash 来实现

int temp[100000] = {0};
void fun(){
	 temp[a[1]] ++;
	 for(int i = 2; i <= n; i ++){
			  if(temp[a[i] + 1]!= 0){
			   a[i] ++;
			  }
			  else temp[a[i]] ++;
	 }
}

得到我们所需要的数组后只需求出该数组的逆序数就行了
我这使用递归的方法，复杂度（NlogN）

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

#include<iostream>
using namespace std;
#include<algorithm>
#include<stack>
#define ll long long
const int N = 5e5 + 10;
ll a[N],b[N];
ll n,cnt=0;
void merge(ll a[],ll l,ll r){
	if (r - l < 1)
		return;
	ll mid = (l + r) >> 1;
	merge(a, l, mid);
	merge(a, mid + 1, r);
	ll i = l, j = mid + 1;
	for (ll k = l; k <= r; k++) {
		if (j > r ||  i <= mid && a[i] <= a[j] )
			b[k] = a[i++];
		else { cnt += mid - i + 1;  b[k] = a[j++]; }
	}
	for (ll k = l; k <= r; k++)
		a[k] = b[k];
}
int temp[300000] = {0};
void fun(){
	temp[a[1]] ++;
	for(int i = 2; i <= n; i ++){
		if(temp[a[i] + 1]!= 0){
			a[i] ++;
		}
		else temp[a[i]] ++;
	}
}
int main() {
	ios::sync_with_stdio(false);
	
    cin >> n;
	cnt = 0;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
	}
	fun();
	merge(a, 1, n);
	cout << cnt << endl;
	return 0;
}