这是一篇题解笔记，也是我的第一篇题解笔记，嗯哼。题目链接：OpenJudge - 2:重要逆序对

题目

总时间限制: 10000ms　单个测试点时间限制: 1000ms　内存限制: 65536kB
描述
给定个数的序列，定义一个数对为“重要逆序对”的充要条件为 且 。求给定序列中“重要逆序对”的个数。

输入
第一行为序列中数字的个数N（1 ≤ N ≤ 200000）。
第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000)，由空格分开。
输出
输出一个整数，为给序列中“重要逆序对”的个数。
样例输入

10
0 9 8 7 6 5 4 3 2 1

样例输出

16

提示
如果使用printf输出long long类型，请用%lld
数据范围
对于40%的数据，有N ≤ 1000。

想法

题目是统计逆序数的变种，那么基本就需要拿计算逆序数的归并算法来改了。这是我之前学习时写的归并排序代码：

typedef long long int lli;
lli arr[MAX], temp[MAX];

lli biMergeCount(lli* src, lli* res, lli Astart, lli Aend, lli Bend){ // 一次二分归并，同时计算前后两列间的逆序数 
    lli answ = 0;
    lli Bstart = Aend+1;
    lli Apos = Astart, Bpos = Bstart, respos = Astart;
    while(Apos<=Aend&&Bpos<=Bend){
        if(src[Apos]<=src[Bpos]){ // 升序排序 
            res[respos++] = src[Apos++];
        }
        else if(src[Apos]>src[Bpos]){
            res[respos++] = src[Bpos++]; answ += Aend-Apos+1; // 统计列间的逆序对，Apos到Aend是左列里值大于右列src[Bpos]的全部位置
        }
    }
    while(Apos<=Aend||Bpos<=Bend){
        if(Apos<=Aend) res[respos++] = src[Apos++];
        else if(Bpos<=Bend) res[respos++] = src[Bpos++];
    }
    for(lli i=Astart; i<=Bend; i++){
        src[i] = res[i];
    }
    return answ;
}

lli doMergeSortCount(lli* src, lli* res, lli start, lli end){ // 整个归并排序流程，同时计算总的逆序数 
    if(start>=end) return 0;
    lli mid = start+(end-start)/2;
    return doMergeSortCount(src, res, start, mid)+doMergeSortCount(src, res, mid+1, end)+biMergeCount(src, res, start, mid, end);
}

尝试1．把biMergeCount方法的排序标准改成重要逆序对的要求：

    while(Apos<=Aend&&Bpos<=Bend){
        if(src[Apos]<=2*src[Bpos]){ // 按前者与“后者*2”的大小关系排序 
            res[respos++] = src[Apos++];
        }
        else if(src[Apos]>2*src[Bpos]){
            res[respos++] = src[Bpos++]; answ += Aend-Apos+1;
        }
    }

结果是错误的。为什么呢？
这样“排序”存在本质问题，排序规则不具有对称性，所以结果也不确定。如果我输入序列src为5 4 3 2 1，这段程序将排序得到2 1 5 4 3；而如果我更改序列为其排列3 5 2 4 1，将会得到1 3 2 5 4。如果对于同样的输入数集，输出竟然不唯一，那么这肯定不是一种有意义的排序。

尝试2．排序标准不变，计数条件改成重要逆序对条件：

    while(Apos<=Aend&&Bpos<=Bend){
        if(src[Apos]<=src[Bpos]){ // 升序排序 
            res[respos++] = src[Apos++];
        }
        else if(src[Apos]>src[Bpos]){
            if(src[Apos]>2*src[Bpos]) answ += Aend-Apos+1; // 为计数单独设置条件
            res[respos++] = src[Bpos++];
        }
    }

结果仍然是错误的，譬如样例这时会输出14，比结果少。
为发现这个错误，需要想象正常的归并排序逆序数统计时两列数之间的结构，比如这个例子：

左（前）边的子列： 3  10  12             25        27  29        32            40  70
右（后）边的子列：             15  17         26            31        33  35

按原本的计数方法，以右列15为基准，左列的25和后边的元素都会被统计在逆序对中；但按尝试2的方式，以右列15为基准，左列的32和后边的元素本来应该被统计，但却被忽略了，这就是问题所在。
因此，每次轮到把右列的元素src[Bpos]放进res归并数组时，都要查询左列里第一个值大于src[Bpos]的位置find，然后将结果增加Aend-find+1。

由于数据量达到，直接线性查找会超时：

        if(src[Apos]>=src[Bpos]){
            int find;
            for(find = Apos; find<=Aend; find ++){
                if(src[find]>2*src[Bpos]) break;
            }
            answ += Aend-find+1;
            res[respos++] = src[Bpos++];
        }

要用二分查找。实际上，原本二分查找的区间缩小我是现写的，并且不太熟练，还要在循环结束后用局部的线性查找来正确定位，比较麻烦。后来才发现C++标准库里有二分查找的函数：upper_bound()和lower_bound()。
它们都接受四个参数，前两个分别是查找的起始地址（含）和结束地址（不含），第三个是被比较的目标值，第四个（可选）是比较规则函数。
默认情况下，upper_bound()返回查找范围内首个值大于目标值的地址，lower_bound()则返回范围内首个值大于等于目标值的地址。这只对于升序序列好用。但指定比较函数后，就能改变上述加粗处的比较规则，如将第四个参数直接填为std::greater<int>()，即可让上述大于变为小于、大于等于变为小于等于，实现降序序列内的查找。
对于数组，用这两个函数的返回值减去数组变量名就会得到查找结果的下标；对于容器vector，返回值则可以作为迭代器使用。

这样就涉及了这个题的全部细节，通过代码如下。

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>

#define MAX 500000
#define IOS_SPEED std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::upper_bound;

typedef long long int lli;

lli arr[MAX], temp[MAX];

lli biMergeCount(lli* src, lli* res, lli Astart, lli Aend, lli Bend){ // 一次二分归并，同时计算前后两列间的逆序数 
    lli answ = 0;
    lli Bstart = Aend+1;
    lli Apos = Astart, Bpos = Bstart, respos = Astart;
    while(Apos<=Aend&&Bpos<=Bend){
        if(src[Apos]<src[Bpos]){ // 升序排序 
            res[respos++] = src[Apos++];
        }
        else if(src[Apos]>=src[Bpos]){
            int find = upper_bound(src+Apos, src+Aend+1, 2*src[Bpos])-src; // 二分查找
            answ += Aend-find+1;
            res[respos++] = src[Bpos++];
        }
    }
    while(Apos<=Aend||Bpos<=Bend){
        if(Apos<=Aend) res[respos++] = src[Apos++];
        else if(Bpos<=Bend) res[respos++] = src[Bpos++];
    }
    for(lli i=Astart; i<=Bend; i++){
        src[i] = res[i];
    }
    return answ;
}

lli doMergeSortCount(lli* src, lli* res, lli start, lli end){ // 整个归并排序流程，同时计算总的逆序数 
    if(start>=end) return 0;
    lli mid = start+(end-start)/2;
    return doMergeSortCount(src, res, start, mid)+doMergeSortCount(src, res, mid+1, end)+biMergeCount(src, res, start, mid, end);
}

void interface(){
    lli nums;
    IOS_SPEED;
    cin >> nums;
    for(lli i=0; i<nums; i++){
        cin >> arr[i];
    }
    cout << doMergeSortCount(arr, temp, 0, nums-1) << "\n";
}

int main()
{
    interface();
    return 0;
}