1.解释为什么要有离散的这么一个过程？

    刚开始以为999.999.999这么一个数字，对于int存储类型来说是足够了。

    还有只有500000个数字，何必要离散化呢？

    刚开始一直想不通，后来明白了，后面在运用树状数组操作的时候，

    用到的树状数组C[i]是建立在一个有点像位存储的数组的基础之上的，

    不是单纯的建立在输入数组之上。

    比如输入一个9 1 0 5 4，那么C[i]树状数组的建立是在，

    下标 0 1 2 3 4 5 6 7 8 9

    数组 1 1 0 0 1 1 0 0 0 1

    现在由于999999999这个数字相对于500000这个数字来说是很大的，

    所以如果用数组位存储的话，那么需要999999999的空间来存储输入的数据。

    这样是很浪费空间的，题目也是不允许的，所以这里想通过离散化操作，

    使得离散化的结果可以更加的密集。

2. 怎么对这个输入的数组进行离散操作？

class node
{
    public:
    int val,order;
};
node in[maxn];

bool cmp(node a,node b)
{
    return a.val<b.val;
}

for(int i=1;i<=n;i++) {scanf("%d",&in[i].val);in[i].order=i;}

        //离散化

        sort(in+1,in+n+1,cmp);

        for(int i=1;i<=n;i++) aa[in[i].order]=i;

假设输入的数据为：9 1 0 5 4

那么放进in里面，其中order用于标记最原始的数据顺序：  

in[1].val=9     in[2].val=1       in[3].val=0      in[4].val=5    in[5].val=4

in[1].order=1   in[2].order=2     in[3].order=3    in[4].order=4   in[5].order=5

Sort排序以后，val,order都要跟着重新换位置：

in[1].val=0     in[2].val=1       in[3].val=4      in[4].val=5    in[5].val=9

in[1].order=3   in[2].order=2     in[3].order=5    in[4].order=4   in[5].order=1

aa[in[i].order]=i，比如in[3].val=0 in[3].order=3 ,

aa操作表示，之前放在order=3的位置，变化大小以后还要放在order=3位置上。至于大小，进过sort以后，in的序号即为大小排第几， 离散化后：

aa[3]=1  aa[2]=2   aa[5]=3  aa[4]=4   aa[1]=5

即把9 1 0 5 4变成5 2 1 4 3，数据变得更加紧凑，各个数据之间的大小关系不变

计算逆序的根本思想在于，输入一个数x，需要统计在X之前已经出现的、且比x大的数目，这些数目之和即为x的逆序，但是比x大的数目不太容易统计，因为用树形数组可以求[1,x]，而不是[x,n]，所以先求出这些已经出现的、且比x小的总数目，用x的编号减去这个总数目即为x的逆序。

当然，这里对数组c[1,x]求和，而数组c[i]表示i是否出现，若是则为1，否则为0

在离散结果中间结果的基础上，那么其计算逆序数的过程是这么一个过程。

1，输入5，   调用upDate(5, 1),把第5位设置为1

X    1 2 3 4 5

C[x]  0 0 0 0 1

计算1-5上比5小的数字存在么？ 这里用到了树状数组的getSum（5） = 1操作，

现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。

2. 输入2， 调用upDate(2, 1),把第2位设置为1

1 2 3 4 5

0 1 0 0 1

计算1-2上比2小的数字存在么？ 这里用到了树状数组的getSum（2） = 1操作，

现在用输入的下标2 - getSum(2) = 1 就可以得到对于2的逆序数为1。

3. 输入1， 调用upDate(1, 1),把第1位设置为1

1 2 3 4 5

1 1 0 0 1

计算1-1上比1小的数字存在么？ 这里用到了树状数组的getSum（1） = 1操作，

现在用输入的下标 3 - getSum(1) = 2 就可以得到对于1的逆序数为2。

4. 输入4， 调用upDate(4, 1),把第5位设置为1

1 2 3 4 5

1 1 0 1 1

计算1-4上比4小的数字存在么？ 这里用到了树状数组的getSum（4） = 3操作，

现在用输入的下标4 - getSum(4) = 1 就可以得到对于4的逆序数为1。

5. 输入3， 调用upDate(3, 1),把第3位设置为1

1 2 3 4 5

1 1 1 1 1

计算1-3上比3小的数字存在么？ 这里用到了树状数组的getSum（3） = 3操作，

现在用输入的下标5 - getSum(3) = 2（包括自己总共有5个数，而这里面包括自己有比自己小的数共有3个，因此前面有3个比它大） 就可以得到对于3的逆序数为2。

6. 0+1+2+1+2 = 6 这就是最后的逆序数

分析一下时间复杂度，首先用到快速排序，时间复杂度为O(NlogN),

后面是循环插入每一个数字，每次插入一个数字，分别调用一次upData()和getSum()

外循环N, upData()和getSum()时间O(logN) => 时间复杂度还是O(NlogN).

最后总的还是O(NlogN).

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = 500005;

struct Node

{

int val;

int pos;

};

Node node[N];

int c[N], reflect[N], n;

bool cmp(const Node& a, const Node& b)

{

return a.val < b.val;

}

int lowbit(int x)

{

return x & (-x);

}

void update(int x)

{

while (x <= n)

{

c[x] += 1;

x += lowbit(x);

}

}

int getsum(int x)

{

int sum = 0;

while (x > 0)

{

sum += c[x];//c是树状数组，reflect[i]对应这里的x

x -= lowbit(x);

}

return sum;

}

int main()

{

while (scanf("%d", &n) != EOF && n)

{

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

{

scanf("%d", &node[i].val);

node[i].pos = i;

}

sort(node + 1, node + n + 1, cmp);   //排序

for (int i = 1; i <= n; ++i) reflect[node[i].pos] = i;   //离散化

for (int i = 1; i <= n; ++i) c[i] = 0;   //初始化树状数组

long long ans = 0;

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

{

update(reflect[i]);//c[x]是树状数组，reflect[i]是下标

//update（x）可以保证x父亲节点的正确性，进而保证后面对x父亲计算getsum的正确

ans += i - getsum(reflect[i]);

//getsum(x)表示统计大小为【1，x】之间的元素之和，如果他们已经存在，那么c[x]=1,否则c[x]=0

}

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

} 

return 0;

}

TreeArray2299