题解
首先，求逆序数对的思路：
1.得到整个数列后，从前往后扫，统计比a[i]小的，在a[i]后面的有多少个
这样做的话，应该是只有n2的暴力作法，没想到更好的方法
2.统计a[i]前面的，且比它大的数
这样做的话，就可以利用输入的时效性，每输入一个数，就把这个数的num[i]值加1，
然后统计比这个数大的数的num和,
因为这里的和一定是在这个数列中比a[i]大，且在它前面出现的数之和，
然后把把这个和加到总逆序数sum里。
这样做的话直接的暴力作法依然是n2，但是，
我们可以在，统计比这个数大的数的num和这一步进行优化，利用线段树求区间域值的复杂度是logn，
所以总体复杂度就降到了nlogn。
再来看这道题，求得初始数列的逆序数后，再求其他排列的逆序数有一个规律，就是
sum = sum + (n - 1 - a[i]) - a[i];
这个自行验证吧，相信很容易得出
最后，拓展一下，如果要求正序数怎么办？很简单，无非是大小调一下
再问，如果要求满足i<j<k,且a[i]>a[j]>a[k]的数对总数怎么办？
可以从中间的这个数入手，统计a[i]>a[j]的对数m，以及a[j]>a[k]的对数n，m*n就是。。。
要求a[i]>a[j]的个数还是一样的，那么a[j]>a[k]的个数呢？
两种思路：
1.得到a[i]>a[j]的对数后，将数列倒过来后再求a[j]<a[k]的对数
2.更简单的做法是，找到规律发现，n = 整个数列中比a[j]小的数 — 在a[j]前面已经出现的比a[j]小的数的个数
即（假设数列是从1开始的） n = (a[j] -1) - (j - 1 - m )
如果不理解模拟一边就明白了。
AC代码：
#include <cstdio> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 5555; int sum[maxn<<2]; void PushUP(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void build(int l,int r,int rt) { sum[rt] = 0; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); } void update(int p,int l,int r,int rt) { if (l == r) { sum[rt] ++; return ; } int m = (l + r) >> 1; if (p <= m) update(p , lson); else update(p , rson); PushUP(rt); } int query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret += query(L , R , lson); if (R > m) ret += query(L , R , rson); return ret; } int x[maxn]; int main() { int n; while (~scanf("%d",&n)) { build(0 , n - 1 , 1); int sum = 0; for (int i = 0 ; i < n ; i ++) { scanf("%d",&x[i]); sum += query(x[i] , n - 1 , 0 , n - 1 , 1); update(x[i] , 0 , n - 1 , 1); } int ret = sum; for (int i = 0 ; i < n ; i ++) { sum += n - x[i] - x[i] - 1; ret = min(ret , sum); } printf("%d\n",ret); } return 0; }