题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意：给你一个n个数的序列，其中组成的数只有0-n，我们可以进行这么一种操作：把第一个数移到最后一个，次数不限。问，在原始数列和最新生成的数列中逆序数最小可以是多少？

刚开始以为需要枚举求逆序数，但最后知道了这个题是有规律的：一个由0-n组成的n个数的数列，当第一个数移到最后一位的时候，整个数列的逆序数会减少x[i]（移动前，后面比他小的），会增加n-x[i]-1（移动后，前面比他大的）。

那么这个题就成了单纯求原始数列的逆序数。

之前求逆序数用过归并，也用过线段树，可惜没总结，当时的题目还需要离散化。现在先总结这个简单的，等继续回顾暑假内容的时候会遇到的。

线段树求逆序数

因为线段树善于解决区间问题，那么我们可以用它快速区间求和，我们把每个数纳入线段树，当新录入一个数之前，统计已经录入的几个数比他大，以此类推，最后的统计和就是逆序数。

代码：

#include 
  
   
#include 
   
     #include 
    
      #define LS rt << 1 #define RS rt << 1 | 1 #define LSON l,m,rt << 1 #define RSON m + 1,r,rt << 1 | 1 #define MID (l + r) >> 1 #define MAX 5000 using namespace std; int num[MAX << 2]; int x[MAX + 10]; inline void pushup(int rt) { num[rt] = num[LS] + num[RS]; } void build(int l,int r,int rt) { num[rt] = 0; if(l == r) return ; int m = MID; build(LSON); build(RSON); } void update(int p,int l,int r,int rt) { if(l == r) { num[rt]++; return ; } int m = MID; if(p <= m) update(p,LSON); else update(p,RSON); pushup(rt); } int query(int ql,int qr,int l,int r,int rt) { if(l >= ql && r <= qr) { return num[rt]; } int m = MID; int ret = 0; if(ql <= m) ret += query(ql,qr,LSON); if(qr > m) ret += query(ql,qr,RSON); return ret; } int main() { int n; while(~scanf("%d",&n)) { int sum = 0; build(0,n - 1,1); 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 ans = sum; for(int i = 0;i < n;i++) { //0-n的数，把第一个数移到最后一位后 //整个数列的逆序数会减少x[i]（移动前，后面比他小的） //会增加n-x[i]-1（移动后，前面比他大的） sum += n - x[i] - x[i] - 1; ans = min(ans,sum); } printf("%d\n",ans); } return 0; }