[洛谷P1908]逆序对

解题报告

题目见洛谷
分析:首先,这道题需要进行一次排序,题目中没有给出数据范围,但是实测需要使用离散化。。//话说离散化真的好烦人啊。。(雾。。
其次,我认为这道题是可以用线段树做的!!!//虽然我没写出来,代码太冗长了(雾。。
总之,还是膜了一发二叉索引树,发现这种神奇的算法真的是太神奇了! 我真的很佩服这个算法的发明者的智商,方法实在太巧妙了。@Peter M. Fenwick
简单介绍一下这个算法:利用二叉树(废话,名字都是二叉索引树。。)进行数据的存储及维护,巧妙地利用补码表示法和二进制数据的特点,进行节点的定位,成功地做到了把时间复杂度压缩到O(log n),继续膜拜发明者。。
以下是代码,为了训练读者的代码阅读能力,本代码不添加注释(虽然是我懒)

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据