4.6.1 数列上的分治法
给定一个1~n的排列，求这个数列中的逆序数对。
我们可以把一个大的数列A分成左右两个子数列B、C，那么数列A中所有的逆序对必定来自于以下三者其一：
(1) i,j都属于左子数列B的逆序对(i,j);
(2) i,j都属于右子数列C的逆序对(i,j);
(3) i属于B而j属于C
对于这(1)和(2)，可以通过递归求得，对于(3)，我们可以对数列C中的每个数字，统计数列B中比它大的数字的个数，再把结果加起来就好。代码如下，复杂度为$O(n\log n)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34typedef long long ll;
//输入
vector<int> A;
ll merge_count(vector<int> &a)
{
int n = a.size();
if(n<=1) return 0;
ll cnt = 0;
vector<int> b(a.begin(), a.begin()+n/2);
vector<int> c(a.begin() + n/2, a.end());
cnt += merge_count(b); //(1)
cnt += merge_count(c); //(2)
//此时b和c就已经分别排好序了
//(3)
int ai = 0, bi = 0, ci = 0;
while(ai < n)s
{
if(bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) //ci == c.size()这个判断是，如果c数列已经全部找完了，剩下的全是b数列里的树，就不能看在有逆序数的存在
{
a[ai++] = b[bi++];
}
else
{
cnt += (n/2 -bi);
a[ai++] = c[ci++];
}
}
return cnt;
}
void solve()
{
printf("%lld\n", merge_count(A));
}