原题目就不描述了，请自己看。
解决一个问题的第一步是定义清楚问题。
首先我们给出逆序对的定义：
对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。
重要的地方在于，一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k]，那么这里
有两个含 a[i] 的逆序对，分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。
那么第二步是分析问题，这里我们可以使用分治法解决问题。
我们将序列从中间分开，将逆序对分成三类：
- 两个元素都在左边；
- 两个元素都在右边；
- 两个元素一个在左一个在右；
因此这就是我们算法的大致框架：
计算逆序对的数量（序列）：
1. 递归算左边的；
2. 递归算右边的；
3. 算一个左一个右的；
4. 把他们加到到一起。
这个时候我们注意到一个很重要的性质，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。这么做的好处在于，如果序列是有序的，会让第三步计数很容易。
如果无序暴力数的话这一步是O(n^2)的。
比如序列是这样的
4 5 6 | 1 2 3
当你发现 4 比 3 大的时候，也就是说右边最大的元素都小于左边最小的元素，那么左边剩下的5和6都必然比右边的所有元素大，因此就可以不用数5和6的情形了，直接分别加上右半边的元素个数就可以了，这一步就降低到了
O(n), 我们知道递归式 T(n) = 2T(n/2)+O(n) = O(nlogn)的，所以排序的成本是可以接受的，并且这一问题下，
可以很自然地使用归并排序。
给出本咸鱼的代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int array[N];
int nums;
unsigned long result = 0;
void merge_sort(int array[], int l, int r)
{
if (l >= r) return;
int mid = ( l + r ) / 2;
merge_sort(array, l, mid);
merge_sort(array, mid + 1, r);
int temp[r - l + 1];
int lptr = l;
int rptr = mid + 1;
int tempptr = 0;
while(lptr <= mid && rptr <= r)
{
if(array[lptr] <= array[rptr])
{
temp[tempptr++] = array[lptr++];
} else {
temp[tempptr++] = array[rptr++];
result += (mid - lptr + 1);//注意这里，是直接加的，后面的不需要比较了。
}
}
while ( lptr <= mid )
{
temp[tempptr++] = array[lptr++];
}
while ( rptr <= r )
{
temp[tempptr++] = array[rptr++];
}
for (int i = l, j = 0; i <= r; i ++, j ++)
{
array[i] = temp[j];
}
}
int main(){
scanf("%d", &nums);
for(int i = 0; i < nums; i++)
{
scanf("%d", &array[i]);
}
merge_sort(array, 0, nums-1);
cout << result;
return 0;
}
参考文献
- y总算法基础课；
- Algorithm Design: Chapter 5.3。
这里有个地方要注意，我也是相同的做法，但是答案会错，具体问题就在于合并的时候，注意合并的条件是array[lptr] <= array[rptr]而y总的模板里面是小于，少了等号会导致相同的数也被计算了数对，刚学算法，如果我的这个提醒提醒很白痴请见谅
兄弟一语点醒梦中人！
感谢大佬！
谢谢你哥，自己看了十几分钟没明白为什么自己多了一个一！
是这样的，如果是
array[lptr]<array[rptr]。那么，下面的
else就变成了array[lptr]>=array[rptr]了，就不满足逆序对的a[i]>a[j]的条件了这个时候我们注意到一个很重要的性质，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。这么做的好处在于，如果序列是有序的，会让第三步计数很容易。----感谢，终于明白了为什么可以排序
大佬你好，我想问一下第一类和第二类情况是怎么算出来的数字呢，第三种情况就是这个公式我听懂了，为什么第一种和第二种情况就可以自动算出来呢？
第三步理解了就好了，因为我们是归并思想，最终是要把左边递归到只有一个数的区间，这样左边第一个区间和第二个区间就可以算出逆序对的数量。然后再一层一层回溯回去。即这题的递归界限就是当区间只有一个数的时候，回忆归并排序。
对对对，我后来也是这么想的，还是怕自己想的不对问一问比较放心，谢谢您的回复！！
我也是初学者，一起加油！
大佬，能在说一下第一类情况和第二类情况是怎么算出来的吗，它递归的时候会执行
、 while(lptr <= mid && rptr <= r)
{
if(array[lptr] <= array[rptr])
{
temp[tempptr] = array[lptr];
} else {
temp[tempptr] = array[rptr];
result += (mid - lptr + 1);
}
这一部分代码吗
确实！这个地方搞懂了整个算法思路就清晰了
这个问题，这么看。y总一开始假设直接可以把前两部种情况可以直接加出来，后边你发的这段代码是完善这个功能。再一开始的这个函数里面，通过一开始的传参，定义中间左右两边，而之前一开始假设的那个调用函数里面也要传参，把参数传到这个大的函数里面，再通过这参数定义中间值，左右两边，这是层层嵌套的，也称回溯。所以那两部分的值就出来了
这句话非常关键
所以本质上只存在一个在左一个在右的情况？因为最后会分成两个数的区间，就都可以用mid-l+1来计算逆序对个数
我也这么觉得 那为什么res还要左边+右边呢
我也是这么认为的
对的，我也是这样想的
我理解的是内部的逆序对已经在上一次开始分别对左右递归的时候计算出来了，所以处理时只要针对一左一右即可
请问一下各位大佬
为什么两个元素在同一边逆序数的个数是归并排序的调用次数？
虽然不确定你的结论是否正确，但是不太建议以这种思路来理解分治/递归算法。在同一边的逆序对是会被分治解决的，也就是说，总存在某个时刻，他们在两边。
我知道，但是y总的代码就是把归并排序调用的次数相加，我就是不明白为什么归并排序的调用次数，就是两个数同时在左边或者在右边的情况？
LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);我还是把视频多看几遍吧
我好像懂了，我觉得可能不存在前面两种情况（两个数在同一边），因为递归最后都是两个区间进行合并，都会变成第三种情况，所以只要把res定义成全局变量就行了。
是不是递归边界就是左端的两个数，然后这两个数就符合第三种方式，这两个数排完之后不断回溯
我不是这样理解的，我是这样理解的，递归到最后区间都是由一个数组成，然后再逐个合并，所有我认为只会出现第3中情况，即一个在左，一个在右
对的，我的差不多也是这个意思，感谢👍
## 总结：
#### y总的思想是：
先假定归并排序把序列进行排序并返回逆序对的数量。
然后当两个数在左边或者右边的时候就是直接调用归并排序返回。
当出现一个在左，一个在右的时候，就是第三种情况，利用多路归并算法进行求解。
而前面两种由于递归的性质最后都会变成第三种情况。
👍
这里我也不懂，看了你的评论理解啦~感谢！
我和你的理解方式一样
总结的真的太好啦
result += (mid - lptr + 1);这一步是为什么呀，不太懂。大佬能解释一下吗
我的理解是 因为归并排序后左边和右边的数组都是有序的，而此时lptr所指的左边数组的数大于右边数组的数，而由于左边数组是有序的，所以lptr所指的数后面的所有数都大于此时rptr指的数，所以lptr后面的所有数都和此时的rptr所指的数 构成了逆序对，而这些数的数量就是 mid - lptr + 1
感谢大佬
因为
a[i]>a[j]且a[i + 1 ... mid] > a[j]所以
a[i ... mid]之间的数都大于a[j]，同时i ... mid < j所以，
a[i ... mid]之间的数都是a[j]的逆序对所以，
result += ( mid -lptr + 1)（目的是把i到mid的数加入到结果中）我发现用线段树也能a
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10; struct tree{ int sum=0,l,r; }; tree t[N]; int add[N]; void build_tree(int l,int r,int id){ t[id].l=l; t[id].r=r; if(l==r)return ; int m=l+r>>1; build_tree(l,m,id*2); build_tree(m+1,r,id*2+1); } void increase_lazy(int id,int num,int n){ t[id].sum+=num*n; add[id]+=num; } void renew_lazy(int id){ increase_lazy(id*2,add[id],t[id*2].r-t[id*2].l+1); increase_lazy(id*2+1,add[id],t[id*2+1].r-t[id*2+1].l+1); add[id]=0; } int big_add(int ql,int qr,int num,int id){ int l=t[id].l; int r=t[id].r; int m=l+r>>1,s=0; if(l==ql&&r==qr){ increase_lazy(id,num,r-l+1); return num*(r-l+1); } renew_lazy(id); if(qr<=m)s+=big_add(ql,qr,num,id*2); else if(ql>m)s+=big_add(ql,qr,num,id*2+1); else { s+=big_add(ql,m,num,id*2); s+=big_add(m+1,qr,num,id*2+1); } t[id].sum+=s; return s; } int query(int ql,int qr,int id){ int l=t[id].l; int r=t[id].r; int m=l+r>>1; renew_lazy(id); if(l>=ql&&r<=qr)return t[id].sum; else if(qr<=m)return query(ql,qr,id*2); else if(ql>m)return query(ql,qr,id*2+1); else return query(ql,m,id*2)+query(m+1,qr,id*2+1); } int n,ans,a[N],b[N],check[N]; map<int,int> mp; signed main(){ //build_tree(1,100000,1); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; build_tree(1,n,1); for(int i=1;i<=n;i++){ cin>>a[i]; mp[a[i]]++; } int id=1,ans=0; for(auto i:mp)mp[i.first]=id++; for(int i=1;i<=n;i++)a[i]=mp[a[i]]; for(int i=1;i<=n;i++){ ans+=query(a[i],a[i],1); if(a[i]-1>=1)big_add(1,a[i]-1,1,1); } cout<<ans; // for(int i=1;i<=n;i++)cout<<a[i]<<' '; return 0; }ptr是pointer（指针）的缩写
分享一下我的核心代码部分：
int a[N], tmp[N]; typedef long long ll; ll ans = 0; ll merge_sort(int q[], int l, int r) { if (l >= r) return 0; int mid = l + r >> 1, i = l, j = mid + 1, k = 0; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); while (i <= mid && j <= r) { if (q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++], ans += mid - i + 1; } while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; return ans; }其实是假设有一个函数可以解决这个问题，分治为左右两边，最后的子问题也即第三种情况经过分析恰好是归并排序才这么做的，这样会容易理解一些。
在归并的过程中计算逆序对数量会不会有重复啊，我也不会验证
不会的。假设目前的左右区间为[l1, mid1], [mid1 + 1, r1]，那么这一层统计的是左区间[l1, mid1]共有多少个逆序对；当返回上一层时，左右区间为[l1, r1], [r1 + 1, r2]，这一层统计的是左区间[l1, r1]共有多少个逆序对……
把 result 写成全局变量是神来之笔。我个人理解，其实根本没有y总说的前两种情况，因为递归的结果，是两个有序数组在比较，而不是数组自身和自身比较。在归并排序的过程中，顺手寻找逆序对即可
咸鱼梦想家
我有一个对这个问题更美妙的解法，这里空白太小，我就不写了。
array好像是c++关键字吧
对的，写这个答案的时候我还是 C++ 初学者，没有意识到 （虽然现在也还是初学者）。
oier自闭
但是array是STL的，如果没有定义那个头文件是没有问题的
为了不冲突还是少用的好，而且说法是引用了头文件，不是定义头文件
嗯
大佬谦虚了，三年前的题解
怪不得我直接复制粘贴报错了
为什么是mid - i + 1而不是j - mid呢
## 你的代码编译错误
#### 下面是正确的代码
#include <bits/stdc++.h> using namespace std; const int N = 100010; int a[N]; int nums; unsigned long result = 0; void merge_sort(int a[], int l, int r) { if (l >= r) return; int mid = ( l + r ) / 2; merge_sort(a, l, mid); merge_sort(a, mid + 1, r); int temp[r - l + 1]; int lptr = l; int rptr = mid + 1; int tempptr = 0; while(lptr <= mid && rptr <= r) { if(a[lptr] <= a[rptr]) { temp[tempptr++] = a[lptr++]; } else { temp[tempptr++] = a[rptr++]; result += (mid - lptr + 1);//注意这里，是直接加的，后面的不需要比较了。 } } while ( lptr <= mid ) { temp[tempptr++] = a[lptr++]; } while ( rptr <= r ) { temp[tempptr++] = a[rptr++]; } for (int i = l, j = 0; i <= r; i ++, j ++) { a[i] = temp[j]; } } int main(){ scanf("%d", &nums); for(int i = 0; i < nums; i++) { scanf("%d", &a[i]); } merge_sort(a, 0, nums-1); cout << result; return 0; }感谢大佬
わたしは
for (int i = l, j = 0; i <= r; i , j ) array[i] = temp[j];请问这个是怎么影响结果的?不是吧temp数组的数复制到array里面吗?删掉为啥会对result产生影响?
那你的array数组是无序的，就不能直接result+=mid-lptr+1了；
这个是对已经计算过逆序对的子数列排序了
如果不排序，就只能保证
a[i]>a[j]时，对于逆序对的条件成立。但是无法保证
a[i+1 ... mid] >a[j]，这时会产生遗漏，就得挨个比较了，于是乎就失去了这个算法的意义懂了
佬，就是那个算左边和右边的怎么算？