本题可以采用 树状数组+离散化 求逆序对 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 离散化 离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的 全/偏序 关系． 通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化． 用来离散化的可以是大整数、浮点数、字符串等等． ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 参考代码 本题还可以用 归并 或 冒泡 来做，具体内容大家可以看其他题解，我这就不做过多展示了

三个版本 归并排序【经典算法】： 冒泡排序： 树状数组：

这也能用归并做，不过有另一道题，这里就先用树状数组

本文章=这个和这个 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 特别鸣谢：@亚洲卷王 AK IOI ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思路 根据@亚洲卷王 AK IOI的“逆序对2”可知，我们可以使用离散化加树状数组解决。 但是我不会离散化怎么办（我真忘了），但是如果这题强在线怎么办。 有的兄弟有的，我们可以使用无旋 Treap 解决（旋转我不懂）。 考虑每个值 xxx，答案即为 xxx 前面的数 >x>x>x 的数的数量。灵活运用无旋 Treap 的分裂，将树分为 ≤x\le x≤x 和 >x>x>x 的两棵树，答案即为右数之和。 代码