树状数组求逆序数原理

《树状数组求逆序数原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Ultra-QuickSortTimeLimit:7000MSMemoryLimit:65536KTotalSubmissions:15773Accepted:5563DescriptionInthisproblem,youhavetoanalyzeaparticularsortingalgorithm.Thealgorithmprocessesasequenceofndistinctintegersbyswappingtwoadjacentsequenceelementsuntilthesequenceissortedinascendingorder

2、.Fortheinputsequence91054,Ultra-QuickSortproducestheoutput01459.YourtaskistodeterminehowmanyswapoperationsUltra-QuickSortneedstoperforminordertosortagiveninputsequence.InputTheinputcontainsseveraltestcases.Everytestcasebeginswithalinethatcontainsasingleintegern<500,000--thelengt

3、hoftheinputsequence.Eachofthethefollowingnlinescontainsasingleinteger0≤a[i]≤999,999,999,thei-thinputsequenceelement.Inputisterminatedbyasequenceoflengthn=0.Thissequencemustnotbeprocessed.OutputForeveryinputsequence,yourprogramprintsasinglelinecontaininganintegernumberop,theminim

4、umnumberofswapoperationsnecessarytosortthegiveninputsequence.SampleInput59105431230SampleOutput60SourceWaterloolocal2005.02.05树状数组，具体的说是离散化+树状数组。这也是学习树状数组的第一题.算法的大体流程就是：1.先对输入的数组离散化，使得各个元素比较接近，而不是离散的，2.接着，运用树状数组的标准操作来累计数组的逆序数。算法详细解释：1.解释为什么要有离散的这么一个过程？刚开始以为999.999.999这么一个数字，对于in

5、t存储类型来说是足够了。还有只有500000个数字，何必要离散化呢？刚开始一直想不通，后来明白了，后面在运用树状数组操作的时候，用到的树状数组C[i]是建立在一个有点像位存储的数组的基础之上的，不是单纯的建立在输入数组之上。比如输入一个91054，那么C[i]树状数组的建立是在，下标0123456789数组1100110001现在由于999999999这个数字相对于500000这个数字来说是很大的，所以如果用数组位存储的话，那么需要999999999的空间来存储输入的数据。这样是很浪费空间的，题目也是不允许的，所以这里想通过离散化操作，使得离散化的结果

6、可以更加的密集。2.怎么对这个输入的数组进行离散操作？离散化是一种常用的技巧，有时数据范围太大，可以用来放缩到我们能处理的范围；因为其中需排序的数的范围0---999999999；显然数组不肯能这么大；而N的最大范围是500000；故给出的数一定可以与1.。。。N建立一个一一映射；①当然用map可以建立，效率可能低点；②这里用一个结构体structNode{intv,ord;}p[510000];和一个数组a[510000];其中v就是原输入的值，ord是下标；然后对结构体按v从小到大排序；此时，v和结构体的下标就是一个一一对应关系，而且满足原来的大小

7、关系；for(i=1;i<=N;i++)a[p[i].ord]=i;然后a数组就存储了原来所有的大小信息；比如91054-------离散后aa数组就是52143；具体的过程可以自己用笔写写就好了。3.离散之后，怎么使用离散后的结果数组来进行树状数组操作，计算出逆序数？如果数据不是很大，可以一个个插入到树状数组中，每插入一个数，统计比他小的数的个数，对应的逆序为i-getsum(aa[i]),其中i为当前已经插入的数的个数，getsum(aa[i]）为比aa[i]小的数的个数,i-sum(aa[i])即比aa[i]大的个数，即逆序的个数但如果数据比较大

8、，就必须采用离散化方法假设输入的数组是91054，离散后的结果aa[]={5,2,1,4,3}