I.Inverse Pair

题目描述:

For a sequence t1…n, we define the weight of it is the number of pairs(i,j) satisfy i<j and ti>tj.

Now give you a permutation a1…n, you need to choose a sequence b1…n satisfies bi∈{0,1} to minimize the weight of sequence c1…n which satisfies ci=ai+bi.

输入描述:
The first line has one integer nn

The second line has n integers a1…n

It’s guaranteed that ai is a permutation of {1,2…n}

1≤n≤2×10^5

输出描述:
Output the minimum weight of c1…nc1…n you can get.

输入
5
4 3 2 5 1

输出
5

思路：
题意是b的每个数字都能加上1或者不变，求排列的逆序对数。
原本求逆序数是要严格大于，即每个数前面有多少个大于这个数的数字，然后求和。
如果a的前面正好有a+1这个数，那么将a加上1就可以减少一个逆序数。所以先预处理一下这个数组，将其中的一部分数+1，后面的就是正常求逆序数的过程。
暴力肯定会超时，这里用树状数组的方法来求解逆序对数

代码：

//树状数组求解逆序对
#include <bits/stdc++.h>
#define N 500050
typedef long long ll;
using namespace std;
struct Tr {ll num;ll j;
};
ll n;
Tr tr[N];
ll inp[N];
ll lowbit(ll x) {return x & -x;
}
bool mycmp(Tr x, Tr y) {return x.j > y.j || (x.j == y.j && x.num > y.num);
}
ll fid(ll x) {ll t = 0;while (x) {t += inp[x];x -= lowbit(x);}return t;
}
void add(ll x) {while (x <= n) {inp[x]++;x += lowbit(x);}
}
int a[200005];
bool p[200005];
signed main() {cin.tie(0)->ios::sync_with_stdio(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];if (p[a[i] + 1]) {a[i]++;}p[a[i]] = 1;}for (int i = 1; i <= n; i++) {tr[i].num = i;tr[i].j = a[i];}ll ans = 0;sort(tr + 1, tr + n + 1, mycmp);for (int i = 1; i <= n; i++) {ll k = tr[i].num;ans += fid(k);add(k);}cout << ans;return 0;
}