题目链接:
HDU 1394 Minimum Inversion Number
题意:
给出一组数,可以将每个数组首的数依次移到数组尾,求整个过程中(包括初始状态)的最少逆序对数。
分析:
用线段树求初始数组的逆序对数。对每个读入的数在线段树中查询之前有多少比它大的数字出现,那么这就是该数的逆序对数,累加就是整个初始数列的逆序对数。然后将读入的数插入到线段树叶子结点中,(指该数字已经出现了),线段树中需要记录区间已经出现数字个数。对于每个从数列首移到数列尾的移动,可以用 tmp+=((n?1?a[i])?a[i]) ;表示。对于每一个后移的