以下思路都是针对从小到大排序的序列的逆序对
- 首先定义什么是逆序对：比如一个序列是从小到大排列的，那么如果$x_i>x_{i+1}>x_{i+2}>…$那么就是逆序对
- 主要思路是，对于n元逆序对，flag数组中的index表示某个序列中的某个等于index的数，而flag[index]的值表示以这个index结尾的n-1元的逆序对的数量
- 假设序列有n个数，数的范围是[0, MAX], 首先搞一个int flag[MAX+1], 该数组的所有值初始化为0，还有一个int result[n]
- 首先看看如何求二元逆序对
- 从左到右扫描序列，对于序列中位置为
i的值x，flag[x]+=1 - 然后此时，以该x结尾的逆序对的数量就是$\sum_{j=x+1}^{MAX}flag[j]$，将这个数量记录在result[i]
- 那么result的数组的和就是逆序对的数量
- 同样的，在刚才flag[x]+=1的步骤，可以输出后面的数与x组成的序对来输出具体的逆序对
- 从左到右扫描序列，对于序列中位置为
- 三元组的，我们已经用上面的方法求出二元的result数组(此处将其记为result_2数组)，此时设另外的两个数组int flag_3[MAX+1], int result_3[n];
- 同样扫描序列，对于位置为
i的数x，取出result_2[i]的值，也就是以该x结尾的二元组逆序对的数量m，然后flag_3[x]+=m。此时flag_3[x]记录了截止目前，以x结尾的二元组逆序对的数量 - 求$\sum_{j=x+1}^{MAX}flag_3[j]$，得到以x结尾的三元组逆序对的数量，记录在result_3[i]中
- 到最后，result_3就是结果
- 同样扫描序列，对于位置为
- 更多元组的也如此思路
- 这是利用数组记录了当前已经有的数，然后新加入的数如果不是该数组中当前index最大的，那么意味着其比之前加入的一些数小，这就形成了逆序对
- 对于n元逆序对，同理，数组记录了当前已有的数
x作为最后一个元素是x的n-1元逆序对的逆序对的数量，然后如果我们往该数组加入一个数，然后这个数不是index最大的，那么其比之前已经加入的一些数小，从而与比他大的数代表的n-1元逆序对形成了更长的逆序对 - 然后，既然这其中，对数组求和很重要，我们就可以利用树状数组优化这个往flag[x]中增加数值然后求和计算出对应result[i]的过程（原始序对中第
i位的值是x）
3p另一种思路：针对三元逆序对，还有一种简单的解法，先把数据按顺序插入，用树形数组记录此时比这个数大的数的数目x，再把数据倒着插入，用另一个树形数组记录此时比这个数小的数的数目y，x*y=以这个数为中心的三元逆数对数目，把各个数计算累计起来即可（来自17级大佬Potatso）