问一下，这题怎么用树状数组呀

AFO蒟蒻选手 @ 2019-08-01 09:57:52

by BIG_Showers @ 2019-08-01 10:03:56

请参照cdq分治

by _LiM @ 2019-08-01 10:05:54

直接做啊

by 紫钦 @ 2019-08-01 10:08:03

用权值树状数组。类似于桶排序。

维护一开始全是 0 的树状数组。

先把序列离散化，离散化后序列中最大的数记为 max 。

从头扫输入的序列，扫到 a_i 时，在树状数组上查询 [a_i,max] 的区间和，加到答案里。

然后再将树状数组中下标为 a_i 的位置做单点修改，值加一。

易知这样的处理方式可以求出逆序对。

by Catalan1906 @ 2019-08-01 10:08:13

@wyf666 自己模拟一下不就好了……逆序对的定义是“ai>aj且i<j”，那就维护一下在j前面有多少个大于aj的啊……

by mendessy @ 2019-08-01 10:08:28

@wyf666 看题解，这道题我逆序对就是没有打离散化调了半天

by AFO蒟蒻选手 @ 2019-08-01 10:08:31

额。。。

by AFO蒟蒻选手 @ 2019-08-01 10:08:43

谢谢各位大佬

by xh39 @ 2019-08-01 10:08:46

@wyf666 这不是二分难题么?

by 紫钦 @ 2019-08-01 10:08:49

不过都要离散化了，可能不如直接归并排序省事？

by Catalan1906 @ 2019-08-01 10:10:30

@紫钦 先用归并排序，然后离散化，最后树状数组（滑稽保命）