“逆序对”归并和线段树两种解法。这道经典题存在于任何一个算法题库中，故单独拿出分析讨论。

暴力

如果仅仅是用暴力、普通的分治方法。遇到数据量较大时内存不够。

归并

归并排序的时间复杂度

用归并法解此题之前先考虑一下，为何归并排序的时间复杂度是$O(nlog_n)$？

答：

首先是分裂，导致大小为n的数组散开形成$log_n$层，然后归并的亮点在于合并这些分裂开的数组：

两个原本有序的数组，合并的复杂度只需要$O( n )$啊！（当然，需要一个长度为n的辅助数组，空间换时间）

如果两个普通数组，合并时两两比较，复杂度就是$O(n^2)$。

分析到这里，再看看我之前写的归并法解此题，完全没领悟到归并的精髓啊！

最终代码

(就是归并排序多加一句对ans操作)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void merge(vector<int> &data,int i1,int j1,int i2,int j2){
    vector<int > tmp;
    int i=i1;
    while (i1<=j1 && i2<=j2){
        if(data[i1]<=data[i2]){
            tmp.push_back(data[i1++]);
        } else{
            tmp.push_back(data[i2++]);
            ans+=j1-i1+1;
        }
    }
    while (i1<=j1)
        tmp.push_back(data[i1++]);
    while (i2<=j2)
        tmp.push_back(data[i2++]);

    for(int x:tmp)
        data[i++]=x;

    return;
}

ans要声明成long long型，因为5e5大小的数组传进来，随便有几个逆序的ans就好大。

注意两个点：

• 二分时要分割成(i,m,m+1,j)

  不要分成(i,m-1,m,j)这样(1,2)区间会被分成:

  (1,0,1,2)无限循环进入(1,2)

• 合并时的条件是(i<=m && m+1<=j)

  要带上等于号！

  因为不能保证两个式子都是小于的。万一有一个等于就无法进入合并了。

  比如(1,2,3,3) 虽然(3,3)不用处理，但是（1,2）要处理啊。

线段树

License

Adopting CC BY-NC-SA 4.0 License Agreement

Share