题意 ：给你一个数列，a1,a2,a3,a4.......an，然后可以求出逆序数，再把a1放到an后，可以得到一个新的逆序数，再把a2放到a1后边，，，，，，，依次下去，输出最小的那个逆序数。
思路 ：用线段树就是查找比当前这个数大的已存入线段树中的个数。比如求a[i],那么就查找当前线段树(a[i]+1,n)中的个数。。然后把a[i]更新到线段树中。。求逆序数的时候法，当把x放入数组的后面，此时的逆序数应该为x没放入最后面之前的逆序总数加上（n-x）再减去（x-1）；sum = sum+(n-x[i])-(x[i]-1)。
这个破题让我很晕的地方，一开始我没注意的是，输入的数据大小是从0到n的范围之内的，所以我还把数据跟下标弄混了来着。。。。
//HDU 1394 #include <stdio.h> #include <string.h> #include <iostream> using namespace std ; const int maxn = 6000 ; struct node { int l,r ; int num,value ; } Node[maxn*4] ; int data[maxn] ; void build(int v,int l,int r ) { Node[v].l = l ; Node[v].r = r ; Node[v].value = 0 ; int mid = (l + r) >> 1 ; if(l == r) return ; build(v*2,l,mid) ; build(v*2+1,mid+1,r) ; } void update(int v,int l,int r) { if(Node[v].l == l&& Node[v].r == r) { Node[v].value ++ ; return ; } int mid = (Node[v].l + Node[v].r) >> 1 ; if(l <= mid) update(v*2,l,r) ;//因为是单点更新，不需要段，所以也没有横跨两个区间 else update(v*2+1,l,r) ; Node[v].value = Node[v*2].value+Node[v*2+1].value ; } int query(int v,int l,int r) { if(Node[v].l == l && Node[v].r == r) { return Node[v].value ; } int mid = (Node[v].l+Node[v].r) >> 1 ; if(r <= mid) return query(v*2,l,r) ; else if(l > mid) return query(v*2+1,l,r) ; else return query(v*2,l,mid)+query(v*2+1,mid+1,r) ; } int main() { int n ; while(~scanf("%d",&n)) { build(1,1,n) ; int sum = 0 ; for(int i = 1 ; i <= n ; i++) { scanf("%d",&data[i]) ; data[i]++ ;//题目中的是从0到n-1，而建树是从1开始建的，所以这里要往右偏移一个 update(1,data[i],data[i]) ; if(data[i] + 1 <= n) sum += query(1,data[i]+1,n) ;//这里+1是因为如果你要找5的逆序数，得从6开始找。 } int minn = 1212112 ; for(int i = 1 ; i <= n-1 ; i++) { sum += ((n-data[i])-(data[i]-1)) ; if(minn > sum) minn = sum ; } printf("%d ",minn) ; } return 0; }