http://acm.hdu.edu.cn/showproblem.php?pid=1394
题意：
给出一串数，每次把第一个数放到最后，求最小逆序数。
思路：
线段树。
每个结点维护3个值，l，r，和num。l和r代表数值的范围，num代表在[l,r]这个范围内出现的数字个数（下标就代表了数值大小）。因为需要求逆序数，所以每新输入一个值，我们先找比它大的数，比如我们输入的值为a，那么此时它的逆序数肯定为[a+1,n]范围内出现的数字个数，然后我们就可以利用线段树自顶而下寻找。最后把这个新增的数添加进线段树里。
计算出一个逆序数之后，其余的逆序数也就好办了，因为每次都是移动第一个数，那么它减少的逆序数为a[i],新增的逆序数为n-1-a[i]。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn = 20000 + 5; 7 8 int a[50005]; 9 int ans; 10 int sum; 11 12 struct node 13 { 14 int l, r; 15 int num; 16 }t[maxn]; 17 18 int n; 19 20 void build(int L, int R, int k) 21 { 22 t[k].l = L; 23 t[k].r = R; 24 t[k].num = 0; 25 if (L == R) return; 26 int mid = (L + R) / 2; 27 build(L, mid, 2 * k); 28 build(mid + 1, R, 2 * k + 1); 29 } 30 31 void update(int x,int k) 32 { 33 if (t[k].l == x && t[k].r == x) 34 { 35 t[k].num = 1; 36 return; 37 } 38 int mid = (t[k].l+t[k].r) / 2; 39 if (x <= mid) update(x, 2 * k); 40 else update(x, 2 * k + 1); 41 t[k].num = t[2 * k].num + t[2 * k + 1].num; 42 } 43 44 45 void query(int L, int R, int k) 46 { 47 if (L <= t[k].l && R >= t[k].r) 48 { 49 ans += t[k].num; 50 return; 51 } 52 int mid = (t[k].l+t[k].r) / 2; 53 if (R <= mid) query(L, R, 2 * k); 54 else if (L > mid) query(L, R, 2 * k + 1); 55 else 56 { 57 query(L, mid, 2 * k); 58 query(mid+1, R, 2 * k + 1); 59 } 60 } 61 62 int main() 63 { 64 //freopen("D:\txt.txt", "r", stdin); 65 int x; 66 while (scanf("%d", &n) != EOF) 67 { 68 build(1, n, 1); 69 70 sum = 0; 71 for (int i = 1; i <= n; i++) 72 { 73 ans = 0; 74 scanf("%d", &a[i]); 75 query(a[i] + 1, n, 1); //统计出大于a[i]的有多少个 76 sum += ans; //累加逆序数 77 update(a[i], 1); 78 } 79 ans = sum; 80 for (int i = 1; i <= n; i++) 81 { 82 sum = sum + n - 2 * a[i] - 1; 83 ans = min(sum, ans); 84 } 85 printf("%d ", ans); 86 } 87 }