【算法分析】 举个例子：将下面两个区间排序 ai：3 4 7 9 R1 = 4 aj: 1 5 8 10 首先将右区间的1取出，放在 tmp 中，此时 1 比每个ai中的元素都小，得到的逆序对的数量是4。tmp：1 然后再将ai和aj比较（直到ai<aj)，ai<aj时将ai的元素发在tmp中。tmp：1 3 4 现在aj>ai,i指向a3的位置，将5放在tmp中，得到的逆序对的数量为2。tmp: 1 3 4 5 以此类推，直到进行完归并排序，每次合并都会求出逆序对的数目为：R1-i+1，最后让 ans 加上R1-i+1得到答案。 【参考代码】 【时间复杂度】 O(nlog2n)O(nlog_2n)O(nlog2 n) 【预计得分】 100pts100pts100pts

当看到题解区全是某并排序身为线段树爱好者的我必须发一篇题解（ 其实逆序对根本没必要用写也麻烦调也麻烦的归并排序，用简简单单的线段树不就好了 放代码： 就是用时有点抽象（）

X03蒟蒻一只，老师带我们写过

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

离散化处理：排序，编号，便于装桶 树状数组：优化前缀和，每次存入后计算一下后面一共有多少个数即可 最后输出答案即可

千万不要来看我的题解 正确代码放最后\color{yellow}{正确代码放最后}正确代码放最后 先上代码在讲解 首先，根据题目可知： 依题意，先打头文件： 题目要我们求一个长度为n的数列中有多少个逆序对（定义自己看题目），那么我们当机立断，定义长度n，统计变量sum,数列a,并输入： 接着，我们需要比较，数组中前后两个变量的大小，打一个双重循环来判断两变量大小，如果前变量大于后变量，那么统计变量加一： 最后输出sum: 代码如下： 真的是这样吗？ 通过看测试样例，我们得出最终代码：