首页 > 代码库 > TreeArray2299

TreeArray2299

 

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小的数字存在么? 这里用到了树状数组的getSum5) = 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小的数字存在么? 这里用到了树状数组的getSum2) = 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小的数字存在么? 这里用到了树状数组的getSum1) = 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小的数字存在么? 这里用到了树状数组的getSum4) = 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小的数字存在么? 这里用到了树状数组的getSum3) = 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]是下标

//updatex)可以保证x父亲节点的正确性,进而保证后面对x父亲计算getsum的正确

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

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

}

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

return 0;

}

TreeArray2299