题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394
题目大意：
给一个数字由0~n-1这n个数字组成的数列，不断地把第一个数字移动到最后，一共得到n个数列。求这n个数列中，逆序数最小是多少。
题目思路：
首先，建一棵线段树，每个节点表示这个区间内已经插入的数字的个数，开始初始化为0.然后没读入一个数字，把这个数字插入得到线段树的叶子节点，然后向上更新父节点。这样，在建树的过程中，就可以统计出每个逆序数，也就是说，可以再插入每个数字的时候，查找已经插入的数字当中，比这个数字大的数字有多少个，直到最后就可以求出这个数列的逆序数。
然后，利用数列的性质。因为每次都是把第一个数字移动到最后，比如这个数字是a，那么显然，比这个数字小的有a个，比这个数字大的有n-1-a个；因为这个数字在最前面，所以当前这个数字的逆序数是a，把这个数字移动到最后之后，这个数字的逆序数是n-1-a，逆序数增加量：n-1-a-a。这样就可以由原来的数列的逆序数求出所有数列的逆序数。好神奇~
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cctype> 6 #include <stack> 7 #include <queue> 8 #include <map> 9 #include <set> 10 #include <vector> 11 #include <cmath> 12 #include <algorithm> 13 #define lson l, m, rt<<1 14 #define rson m+1, r, rt<<1|1 15 using namespace std; 16 typedef long long int LL; 17 const int MAXN = 0x3f3f3f3f; 18 const int MIN = -0x3f3f3f3f; 19 const double eps = 1e-9; 20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1}, 21 {1,1},{1,-1},{-1,-1}}; 22 const int MAX = 5000+10; 23 int a[MAX<<2], n, b[MAX]; 24 void pushup(int rt) 25 { 26 a[rt] = a[rt<<1] + a[rt<<1|1]; 27 } 28 void build(int l, int r, int rt) 29 { 30 if (l == r) { a[rt] = 0; return; } 31 int m = (l + r) >> 1; 32 build(lson); build(rson); pushup(rt); 33 } 34 void update(int p, int l, int r, int rt) 35 { 36 if (l == r) { a[rt]++; return; } 37 int m = (l + r) >> 1; 38 if (p <= m) update(p, lson); 39 else update(p, rson); 40 pushup(rt); 41 } 42 int query(int L, int R, int l, int r, int rt) 43 { 44 if (L <= l && R >= r) { return a[rt]; } 45 int m = (l + r) >> 1, ret = 0; 46 if (L <= m) ret += query(L, R, lson); 47 if (R > m) ret += query(L, R, rson); 48 return ret; 49 } 50 int main(void){ 51 #ifndef ONLINE_JUDGE 52 freopen("hdu1394.in", "r", stdin); 53 #endif 54 while (~scanf("%d", &n)){ 55 int i, j, sum; build(0, n - 1, 1); 56 sum = 0; 57 for (i = 0; i < n; ++i){ 58 scanf("%d", b + i); 59 sum += query(b[i]+1, n - 1, 0, n - 1, 1); 60 update(b[i], 0, n - 1, 1); 61 } 62 int ans = sum; 63 for (i = 0; i < n; ++i){ 64 sum += (n - 1 - b[i] * 2); 65 ans = min(ans, sum); 66 } 67 printf("%d\n", ans); 68 } 69 70 return 0; 71 }
现在写点更新的线段树比以前熟练一点了~接下来练区间更新的。