algo1
分治+归并排序
对于数据num
result[i]表示 j >i 中, num[j] < num[i]的元素数。
对于数组
首先将数组分为两部分,,以及
对数组 和
进行升序排序,对排序后数组进行归并排序,由semiCount记录合并到最终数组中来自
的元素数量,由indice[i]记录排序后的数组中,下标为i的元素对应的原数组中的下标。
对于当前归并迭代,如果待插入元素e来自 ,则result[indice[index_of(e)] 更新为 result[indice[index_of(e)]] += semiCount; 如果e来自于
,则 result[indice[index_of(e)]]保持不变,并且semiCount++
由于对当前数组进行操作的时候,需要引用子数组的结果,因此,需要对左右两个数组先进行操作。