题目大意：

给出长度为n的序列，每次只能交换相邻的两个元素，问至少要交换几次才使得该序列为递增序列。

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define mem(a) memset(a,0,sizeof(a))

#define MIN(a , b) ((a) < (b)   (a) : (b))

#define MAXN 500010

#define INF  1000000007

#define lson k<<1,     l,     mid

#define rson (k<<1)|1, mid+1,  r

using namespace std;

int Tree[MAXN<<2], index[MAXN], num[MAXN];

int N;

int cmp(const int i, const int j)

{

    return num[i] < num[j];

}

void Edit(int k, int l, int r, int num, int value)// Edit(1, 1, N, i, 1);//Edit(1, 1, N, index[i], -1)

{/*线段树对应的情况为【1,5】：【1,3】【4,5】\\[1,2][2,3][4,4][5,5]\\[1,1][2,2][3,3][4,4][5,5]

i从1到N（离散化的N数）。线段树[3,3]表示原始数第三个位置的数0，是否还在树里面。另外根节点更新时，

子节点也更新，即有PUSHDOWN，PUSHUP没有*/

    Tree[k] += value;

    if(r==l) return ;

    int mid = (l+r) >> 1;

    if(num <= mid) Edit(lson, num, value);

    else Edit(rson, num, value);//#define rson (k<<1)|1, mid+1,  r

}

int Search(int k, int l, int r, int L, int R)//L,R是要找的区间

{//Search(1, 1, N, 1, index[i])

    if(L<=l && r<=R) return Tree[k];

    int mid = (l+r) >> 1;

    int ans = 0;

    if(L <= mid) ans += Search(lson, L, R);

    if(R > mid) ans += Search(rson, L, R);

    return ans;

}

int main()

{

    while(~scanf("%d", &N) && N)

    {

        mem(Tree); mem(num); mem(index);

        for(int i=1;i<=N;i++)

        {

            scanf("%d", &num[i]);

            Edit(1, 1, N, i, 1);

            index[i] = i;

        }

        sort(index+1, index+N+1,cmp);

        long long ans = 0;

        for(int i=1;i<=N;i++)

        {

            ans += (Search(1, 1, N, 1, index[i])-1);//在[1,index[i]区间内有多少个数，这些数都是比当前的数小]

            Edit(1, 1, N, index[i], -1);//统计之后，除去该点,在线段树里，即表示除去index[x]位置的数

/*

num：   9  1  0  5  4

index：  1  2  3  4  5

排序后：

num：   0  1  4  5  9

index：  3  2  5  4  1

即index[1]=3,index[3]=5

num：                 0  1  4  5  9

前面比自己大的数      2  1  2  1  0

index[1]表示最小数的位置，（此时线段树里只有它自己最小，

因此它前面有多少个数，即表示该数的逆序是多少），第二次

index[2]表示第二小的数，考虑它前面有多少个存在的数*/

        }

        printf("%I64d\n", ans);

    }

    return 0;

}

TreeSegment2299