二分与分治基础

Andy Shen2024/7/13大约 17 分钟

零、Introduction

本文将分为四章，主题为二分法与分治。对于入门同学，学习第一、二章中的 1-3 小节即可，关键在于把握二分和分治的核心思想，有所感悟；对于进阶同学，可以额外学习第一章的第 4 小节，这一部分提供了一些实战中的习题，可以帮助你快速掌握二分法，也可以一并学习第二章的第 4 小节，对 cdq 算法有更多的认识；对于基础比较扎实的同学，可以自行学习余下部分，这些部分不做具体要求，且基本上需要有其他算法的学习基础（如树状数组、线段树等）。

一、二分

为了讨论方便，本章中所有序列不做说明则默认是单调增序列。

0.暴力查找和优化的暴力查找

首先我们先提出一个问题：如果有一个序列，我要从这个序列当中找到某个元素所在的位置，那么，我们应该怎么实现？

显然的，我们枚举这个序列当中的元素，然后和我的元素一一比较，相同输出位置即可：

int a[N];
int n,x;
cin >> n >> x;
for(int i=1; i<=n; i++) {
    if(a[i]==x) {
        cout << i << endl;
        break;  // Not hungry
    }
}

假如，我们这个序列是有序的呢？这样子一一比较是不是就显得有点“蠢”呢。

举个例子：我要在 $2, 4, 6, 8, 10, . . ., 10000$ 这个序列里面找到 5000 所在的位置，那么，你可能就会觉得，5000 那么大，和 10，20 这些较小的元素比较好像是没有什么特别大的意义的。我们考虑这样一种思路：每次 10 个 10 个跳，当第一次跳过头的时候，我们回头再找到答案不就行了吗。

int a[N];
int n,x;
int pos=-1;
int i;
for(i=1; i<=n; i+=10) {
    if(a[i]==x) {
        pos=i;
        break;
    }else if(a[i]>x) {
        for(int j=i;j>=i-10;j--) {
            if(a[j]==x) {
                pos=j;
                break;
            }
        }
        if(pos==-1) {
            break;
        }
    }
}
for(;i<=n;i++) {
    if(a[i]==x) {
        pos=i;
        break;
    }
}
cout << pos << endl;

我们考虑一下这个方法的本质：当我找到第一个找过头的 $i$ ，也就是符合 $a [i] >= x \land a [i - 10] < x$ $^{1}$ ，那么我的答案 $x$ 是不是一定在 $[i - 10, i]$ 这个范围内 $^{2}$ 。接下来我是不是只要在这个被缩小了的范围里面寻找答案即可？

这个 10 个 10 个的找在个数少的时候是不是看起来快很多，但是假如说有 100000 个元素呢，10 个 10 个找是不是也要找 10000 次？那么我们是不是要想办法尽可能最大化这个值呢？另外，在这个缩小成 10 的区间内，我们是不是也可以不一个个找，而是类似的隔几个找一下呢？当你发现这两个问题的时候，恭喜你，你已经想到二分法了。

1.二分查找

二分查找的思路是在我们上面陈述的“改进的”暴力法当中的再改进。和前面 10 个 10 个不同，我们可以考虑区间的长度后尽可能大的缩小区间。二分法的实质就是每次排除一半的元素。我们考虑中间位置 $m i d$ ，假如 $x < a [m i d]$ ，那么答案肯定在左半部分 $[l, m i d - 1]$ ；假如 $x > a [m i d]$ ，答案肯定在右半部分 $[m i d + 1, r]$ 。和刚刚在 10 个元素内暴力搜索不同，在这里我们对于左边部分和右边部分，我们可以进行类似的操作，直到最后我们的答案区间只剩下一个元素（即 $l == r$ ）为止。

int a[100];
int n, x;
cin >> n >> x;
int l = 1, r = n;
while (l < r) {
    int mid = (l + r) >> 1;
    if (x <= a[mid])
        r = mid;
    else
        l = mid + 1;
    // cout << l << ' ' << r << endl;
}

但是这个方法和刚刚的“改进”的暴力算法都有一个适用的前提条件：必须是单调序列当中才能使用！不然的话你是并不知道被你“排除掉”的那一部分当中是不是仍然可能存在答案。

2.STL 中的二分查找

事实上，在实际应用中二分查找使用的非常广泛，所以 STL 里面也默认提供了四个用于二分查找的函数：lower_bound() upper_bound() binary_search() equal_range()。

首先我们解释一下lower_bound()和upper_bound()之间的差别，前者返回第一个不小于查找元素的位置（指针或迭代器）；后者返回第一个大于查找元素的位置。我举个例子，假如说原序列为{1,2,3,3,3,4}，那么使用lower_bound()就会返回第三个元素的位置；而使用upper_bound()就会返回第六个元素的位置。

equal_range()是lower_bound()和upper_bound()的混合。从cppreference不难看出它返回一个分别计算了lower_bound()和upper_bound()的pair：

template<class ForwardIt,
         class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
constexpr std::pair<ForwardIt, ForwardIt>
    equal_range(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    return std::make_pair(std::lower_bound(first, last, value, comp),
                          std::upper_bound(first, last, value, comp));
}

binary_search()最简单也最“没用”。它返回一个bool值，表示你查找的元素是否在该区间当中。

3.二分答案

我们将刚刚二分查找的适用范围拓宽一下。我们刚刚讨论的是在给定的一个有序序列当中查找位置；我们将有序序列拓展到一个单调函数f()，然后将原来的“位置”拓展到这个单调函数的取值范围。那么，我们就可以从这个单调函数中找到最接近我想要查找的值x时的取值。

这样说可能比较抽象，我们举个比较简单易懂的例子吧。如果你家要铺地砖，每平米的价格和你要铺的平米数存在 $c = 50 x$ 的关系，现在，你有 10000 块，你最多能铺多少平米地砖？

对于这个问题，我们很容易就得到总花费 $s = 50 x^{2}$ 。然后我们要求出 $s \leq 10000$ 时最大的 $x$ 。这个时候可能有同学会要说了：我可以用数学方法做！那么这是由于这个例题当中的 $s$ 比较简单，当 $s$ 比较复杂的时候，数学方法就不可行了。那么，显然的，我们可以一一枚举 $x$ ，然后当 $s$ 第一次大于 10000 的时候就终止。这个办法就类似二分查找里面的暴力法。

那么，我们类比一下，这里是不是也能够使用二分法呢？我们观察发现， $s$ 这个函数在大于零的时候具有单调性。也就是， $x$ 越大， $s$ 一定越大。那么，我们可以二分枚举出 $x$ ，如果大了，就去较小的那半区间找答案，反过来也是一样。

int sMax;
cin >> sMax;
int l = 1, r = sMax;
while (l < r) {
    int mid = (l + r) >> 1;
    if (50*mid*mid <= sMax)
        r = mid;
    else
        l = mid + 1;
}

接下来，我们要对这个过程进行一定的封装：也就是我们经常见到的check()函数。check()函数当且仅当目前答案符合前提条件（也就是这里的 $s \leq 10000$ ）的情况下返回true。这是一种习惯，因为有的时候你对前提条件的判断是比较复杂的，那么封装成一个函数会使得你的代码看起来更清楚。

bool check(int x,int sMax)
{
    return 50*x*x<=sMax;
}

int sMax;
cin >> sMax;
int l = 1, r = sMax;
while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid))
        l = mid;
    else
        r = mid - 1;
}

4.二分的综合运用

（高精度）开方

高精度不高精度，本身并不重要。高精度在封装之后也就是和我们int long long一样的类型。所以，我们只需要知道如何使用二分法计算出开方后的答案 $x$ 。从上一题中我们其实就能够很容易推出怎么使用二分法开方。假如我当前数为 $n$ ，那么显然的， $x^{2} \leq n$ 中最大的 $x$ ，就是最接近 $\sqrt{n}$ 的答案。

bool check(BigInt x,BigInt sMax)
{
    return x*x<=sMax;
}

BigInt n;
cin >> n;
BigInt l = 1, r = n;
while (l < r) {
    BigInt mid = (l + r) / 2;
    if (check(mid))
        r = mid;
    else
        l = mid + 1;
}

（高精度）快速幂

说到快速幂这个事情，我们先要知道这两个式子： $k^{a} \cdot k^{b} = k^{a + b}$ ， $(k^{a})^{b} = k^{a * b}$

然后，快速幂解决的是这样一个问题：快速的求出 $k^{n}$ 的值。那么，使用刚刚上面这个式子，我们可以将 $n$ 拆分成若干个数的和。

快速幂的核心思想，就是将 $n$ 拆分成若干个 $2$ 的幂的和，比如这样：

k^{n} = k^{a_{0} * 2^{0} + a_{1} * 2^{1} + \dots + a_{t} * 2^{t}} = k^{a_{0} * 2^{0}} * k^{a_{1} * 2^{1}} * \dots k^{a_{t} * 2^{t}}

，其中 $n = a_{0} * 2^{0} + a_{1} * 2^{1} + \dots + a_{t} * 2^{t}, a_{i} \in {0, 1}$

在这个变化当中， $k^{2^{i}} = k^{2^{i - 1} * 2} = (k^{2^{i - 1}})^{2}$

你看，这是不是就有点动态规划的味道了？我们可以使用 $k^{2^{i - 1}}$ 来推导出 $k^{2^{i}}$ 的值。那么，我们实际计算的时候就把这个值叫做base，然后这个base代表了这一位的答案最后我们要从小到大开始计算``。

以上，我们将 $n$ 拆分成了二的幂的和，然后求 $k^{n}$ 时，我们可以直接将它拆分成这些数的乘积，最后我们要进行的乘法的次数就是 $n$ 在二进制下的位数，也就是 $\log_{2} (n)$ ，极大的加快了速度。

BigInt quickpow(BigInt k,BigInt n)
{
    BigInt base=k,ans=1;
    while(n) {
        if(n&1) {   // n的最低位为1
            ans*=base;  // 乘上当前这一位的base
        }
        n>>=1;  // 右移，计算下一位
        base*=base; // 计算下一次对应的base。
    }
    return ans;
}

二分答案习题——数列分段

最长不下降子序列——导弹拦截

二、分治

1.归并排序

引入：二路归并

首先我们考虑一个简单的问题：你有两个已经排好序的数组，怎么样把它合并成一个有序的新数组。

这个问题很简单：准备一个空数组，然后两个数组里面头部最小的元素丢进去，如果某个数组已经丢完了，那么把另外一个数组的剩余元素一股脑丢进去就行：

int pos1,pos2,pos;
int lenA,lenB;
int a[N],b[N]
int ans[N+N];
// 输入输出略，以下为归并过程。
while (pos1 <= lenA && pos2 <= lenB) {
    if (a[pos1] <= b[pos2]) {
        ans[pos] = a[pos1];
        pos++;
        pos1++;
    } else {
        ans[pos] = b[pos2];
        pos++;
        pos2++;
    }
}
while (pos1 <= lenA) {
    mem[pos] = a[pos1];
    pos++;
    pos1++;
}
while (pos2 <= lenB) {
    ans[pos] = b[pos2];
    pos++;
    pos2++;
}

上面这个东西就叫做二路归并。

正题

归并排序，其实就是使用二路归并的排序。首先，我们要承认一个很客观的事实：一个元素所组成的数组一定是有序的。那么我们现在有两个这样子一个元素的数组，我们要组成一个新的长度为 2 的数组，那么是不是使用上面的二路归并即可。如果从长度为 2 到长度为 4 呢？再多呢？是不是按照这个思路下去，我最后就可以得到一个有序的序列？按照这个思路，就得到了归并排序。

从前面看出归并排序是自底向上的一个过程。那么我们如何构造出这个过程呢？我们可以使用二分+递归。每一次将数列分成两部分，直到无法再分为止，然后自底向上的依次进行归并。

void merge_sort(ll mem[], int l, int r)
{
    if (l >= r) {   // 区间只剩下一个元素，返回
        return;
    }
    int mid = (l + r) >> 1;
    merge_sort(mem, l, mid);
    merge_sort(mem, mid + 1, r);
    int posL = l, posR = mid + 1;
    int pos = l;
    while (posL <= mid && posR <= r) {  //将[l,mid]部分和[mid+1,r]部分合并
        if (a[posL] <= a[posR]) {
            mem[pos++] = a[posL++];
        } else {
            mem[pos++] = a[posR++];
        }
    }
    while (posL <= mid) {
        mem[pos++] = a[posL++];
    }
    while (posR <= r) {
        mem[pos++] = a[posR++];
    }
    for (int i = l; i <= r; i++) {
        a[i] = mem[i];
    }
}

2.统计两有序区间内的逆序对

首先我们要知道逆序对的概念：对于 $i < j$ ，存在 $a_{i} > a_{j}$ ，那么我们认为 $(i, j)$ 构成一组逆序对。简单来说，就是在如果我们认为前小后大正常，那么前大后小就是逆序对。

我们考虑这样一个问题：我有一个序列，它的左半部分和右半部分都是有序的，那么问这个序列中存在多少对逆序对。显然的，左边部分内部和右边部分内部是不存在逆序对的（因为前提说了有序）。

首先我们考虑一个很 naive 的做法：我们分别枚举两区间中元素，然后比较是否是逆序对：

int l,r,a[N];
//l,r,a输入此处略去
int mid=(l+r)>>1;
int ans=0;
for(int i=1; i<=mid; i++) { // 假设[l,mid]和[mid+1,r]间元素是有序的
    for(int j=mid+1; j<=r; j++) {
        if (a[i]>a[j]) {
            ans++;
        }
    }
}

这个办法当中其实显然存在一个简单的优化：对于左边某一元素 $a_{i}$ ，它如果大于右边的某元素 $a_{j}$ ，那么由于左半部分是单调递增的，也就是在 $[i, m i d]$ 中的所有元素都大于 $a_{i}$ 。所以在 $[i, m i d]$ 中的所有元素，都大于 $a_{j}$ 。从这一点出发，对于某一 $a_{i} > a_{j}$ ，我们就不需要枚举之后的 $i$ ，直接统计答案然后 $j$ 向右移即可。我们可以使用双指针：如果 $a_{i} > a_{j}$ ，那么答案加上 $m i d - i + 1$ ，然后 $j$ 向右一个位置；如果 $a_{i} < a_{j}$ ，那么就 $i$ 向右一个位置。最后，当 $i$ 和 $j$ 任意一个达到结尾就结束计算。

3.从归并到 cdq 求逆序对

上面这个 $i$ 和 $j$ 的移动过程，是不是有点像二路归并？这个逆序对的求解方式需要左右区间都有序，而二路归并正好符合这个条件。所以我们就可以将这两部分结合起来求逆序对，这也就是著名的 cdq 算法。 $^{3}$

这个过程，就是在二路归并的时候，如果发现左区间的某个元素大于右区间的某个元素，统计一次答案。然后，我们将左区间内部的答案和右区间内部的答案和跨区间的答案相加，就得到了最后的总答案。

ll cdq(ll mem[], int l, int r)
{
    if (l >= r) {
        return 0;
    }
    int mid = (l + r) >> 1;
    ll lAns = cdq(mem, l, mid); //统计左区间答案
    ll rAns = cdq(mem, mid + 1, r); //统计右区间答案
    ll ans = 0;
    int posL = l, posR = mid + 1;
    int pos = l;
    while (posL <= mid && posR <= r) {
        if (a[posL] <= a[posR]) {
            mem[pos++] = a[posL++];
        } else {
            mem[pos++] = a[posR++];
            ans += mid - posL + 1;  //统计跨区间答案
        }
    }
    while (posL <= mid) {
        mem[pos++] = a[posL++];
    }
    while (posR <= r) {
        mem[pos++] = a[posR++];
    }
    for (int i = l; i <= r; i++) {
        a[i] = mem[i];
    }
    return lAns + rAns + ans;//返回总答案
}

4.cdq 的本质

cdq 的本质是：使用归并过程中对两个区间元素相互之间的比较进行某种特殊关系的答案统计。

我们以前文的逆序对为例：假如我们将一个元素在原序列的顺序也记录下来作为 $c_{i}$ ，那么，我每个元素就是一个数对 $(c_{i}, a_{i})$ 。显然，原序列关于 $c_{i}$ 一定有序（这里需要这么提一下是为了下面的三维偏序做铺垫），也就是 $\forall i < j, c_{i} < c_{j}$ ，然后我们要处理所有 $a_{i} > a_{j}$ 。于是，我可以使用分治的思想：在左半区间的元素 $a_{i}$ 如果比在右半区间的某个 $a_{j}$ 大，那么，统计答案，怎么统计前面也讲过了此处不过多赘述了。

5.三维偏序（陌上花开）*

5.0 前置：树状数组

OIWiki

5.1 实战

首先我们来看看三维偏序问题是怎么样的：统计符合 $i, j \in [1, n], a_{i} < a_{j} \land b_{i} < b_{j} \land c_{i} < c_{j}$ 的 $(i, j)$ 的个数

前一节中，我提到要记录在原序列中的顺序，是因为对于三维偏序问题，第一维的顺序不一定是某个元素在原序列当中的顺序，那么我们要先按照某一个属性先进行一次排序（此处我们选 $a_{i}$ ），排序之后，我们分割左右区间的时候就能保证 $\forall a_{i} \in L, a_{j} \in R, a_{i} < a_{j}$ ，也就是保证左右区间绝对偏序。接下来，我们对左右区间内部，按照 $b_{i}$ 进行排序（这里可以直接调用sort函数，当然也可以二路归并）。在左右区间内部排序后，我们类似前文求逆序对一样，如果，那么此时我们统计这一段内可以产生的偏序对个数，就是答案，在这个偏序对求解当中，通常会使用树状数组，这也在上一节进行了解释了。

#include <bits/stdc++.h>

using namespace std;

// Structs
constexpr int MAX_N = 200010;
struct Element {
    int a, b, c;
    int cnt, res;
    bool operator<(const Element& rhs) const
    {
        return this->a == rhs.a ? this->b == rhs.b ? this->c < rhs.c : this->b < rhs.b : this->a < rhs.a;
    }
    bool operator==(const Element& rhs) const
    {
        return this->a == rhs.a && this->b == rhs.b && this->c && rhs.c;
    }
} elems[MAX_N];

map<Element, int> melem;

// Global variables
int n, k, res[MAX_N];

// Binary Indexed Tree
int BIT[MAX_N << 1];

inline int lowbit(int x)
{
    return x & (-x);
}

void add(int x, int v)
{
    while (x <= k) {
        BIT[x] += v;
        x += lowbit(x);
    }
}

int sum(int x)
{
    int ans = 0;
    while (x) {
        ans += BIT[x];
        x -= lowbit(x);
    }
    return ans;
}

// cdq divide and conquer

void cdq(int l, int r)
{
    if (l >= r) {
        return;
    }
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(elems + l, elems + mid + 1, [](const Element& lhs, const Element& rhs) -> bool { return lhs.b == rhs.b ? lhs.c < rhs.c : lhs.b < rhs.b; });
    sort(elems + mid + 1, elems + r + 1, [](const Element& lhs, const Element& rhs) -> bool { return lhs.b == rhs.b ? lhs.c < rhs.c : lhs.b < rhs.b; });
    int posL = l, posR = mid + 1;
    while (posR <= r) {
        while (posL <= mid && elems[posL].b <= elems[posR].b) {
            add(elems[posL].c, elems[posL].cnt);
            posL++;
        }
        elems[posR].res += sum(elems[posR].c);
        posR++;
    }
    for (int i = l; i < posL; i++) {
        add(elems[i].c, -elems[i].cnt);
    }
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        Element tmp = {};
        cin >> tmp.a >> tmp.b >> tmp.c;
        melem[tmp]++;
    }
    int m = 0;
    for (auto it : melem) {
        elems[++m] = { it.first.a, it.first.b, it.first.c, it.second, 0 };
    }
    cdq(1, m);
    for (int i = 1; i <= m; i++) {
        res[elems[i].res + elems[i].cnt - 1] += elems[i].cnt;
    }
    for (int i = 0; i < n; i++) {
        cout << res[i] << endl;
    }
    return 0;
}

三、离线算法基础*

离线算法简介

离线算法，是相对于在线算法而言的：在线算法是询问时调用子程序直接回答；离线算法是读入所有询问后一并处理回答。我们通过一个简单的例子来解释他们的差别：假如我有一个加法机器，每次读两个数，返回加和，那么使用在线算法写出来就是这样的：

int n;
cin >> n;
for(int i=1; i<=n; i++) {
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
}

这个程序，每当读入一次 a,b，就会立刻返回答案。而离线算法是这样的

struct Query{
    int a,b;
}qs[MAX_N];
int n;
cin >> n;
for(int i=1; i<=n; i++) {
    cin >> qs[i].a >> qs[i].b;
}
for(int i=1; i<=n; i++) {
    cout << qs[i].a << qs[i].b;
}

上面这个程序，会将所有询问的 a,b 全部暂存下来，然后统一去回答问题。至于为什么这么做，简单来说就是：你处理某个询问时，可能会有一部分信息对其他的的询问也有用处，那么，使用离线的算法，然后通过排序等方式将需要内容“类似”的询问全部存下来，然后再统一输出即可。

通过构造进行询问回答

四、整体二分 $^{4}$ *

本章待补

Notes&References

1. $\land$ 是逻辑学上的写法，又叫析取，相当于 C++里面的逻辑与

2.[a,b]等同于 a~b 的范围

3.该思路由 2008 年 IOI 金牌获得者陈丹琦在国家集训队论文中系统的归纳总结(https://www.cs.princeton.edu/~danqic/papers/divide-and-conquer.pdf)，后被国内 OI 圈称为 cdq 算法。

4.《算法竞赛进阶指南》P247-P251（李煜东著，河南电子音像出版社）