树状数组写起来真短- -。。
先利用树状数组求出原逆序对的个数
比如第i个是A[i],那么就加上[A[i],n]区间内的sum和，然后再把A[i]更新成1
然后怎么通过原逆序对推出它移动以后的逆序对呢
我们来举例，假如A[1]为3，n为5，那么比A[1]小的，排在3后面的，有1和2，也就是A[1]-1
现在我们把A[1]移动到了最后，所以以前有A[1]参与的逆序对就没了，变成了ans-(A[1]-1)
但是又会得到新的一些逆序对，因为以前的3跑到了最后面，那么现在有哪些比3大在3的前面呢，当然就是n-A[1]个啊
所以变成了ans-2*A[1]+1
然后按照变换，再维护最小值就行了
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<iostream>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;const int MX = 5e3 + 5;
const int INF = 0x3f3f3f3f;int S[MX], A[MX], n;int query(int x) {int ret = 0;for(; x; x -= x & -x) {ret += S[x];}return ret;
}void update(int x, int d) {for(; x <= n; x += x & -x) {S[x] += d;}
}int main() {while(~scanf("%d", &n)) {memset(S, 0, sizeof(S));for(int i = 1; i <= n; i++) {scanf("%d", &A[i]); A[i]++;}int sum = 0;for(int i = 1; i <= n; i++) {sum += query(n) - query(A[i] - 1);update(A[i], 1);}int ans = sum;for(int i = 1; i <= n - 1; i++) {sum += n - 2 * A[i] + 1;ans = min(ans, sum);}printf("%d\n", ans);}return 0;
}