位运算，递推与递归，前缀和与差分，二分与三分，排序，倍增，贪心，双指针，高精度，离散化，区间合并

基础技巧

略过看似基础内容的高水平读者，比略过看似复杂内容的低水平读者，可能要错失更多东西。-G.波利亚

Base is not easy.

并不复杂的基础技巧可以在各种地方灵活应用，所以从某种程度来说，这部分的应用是很难的。

学过一定量的东西之后，要学会思考。

CF里就喜欢考这种简单的算法。

位运算

主要是在这里记录一些坑点和技巧：

• 判断数i的第j位是否为1，可以是(i >> (j - 1)) & 1或者i & (1 << (j - 1))，但是注意后者计算结果不一定是1，不能看后者是否等于1。
• 链式前向星中正反向边的成对变换：假设edge[i]是a到b的边，那么edge[i ^ 1]就是这条边的反向边。
• 有时候要开long long，防止长度爆掉。
• >>运算是符号右移。

递推与递归

现在看来没有专门整理的必要了，用到的太多了。

前缀和与差分

前缀和

一维前缀和基本没什么好说的。

二维前缀和的预处理为：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
     	sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + a[i][j] - sum[i - 1][j - 1];   
    }
}

有时候二维前缀和卡空间，可能要原地做前缀和：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
     	sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];   
    }
}

二维前缀和的查询：

假设要查询以(i, j) 和(k, l)为对角顶点（包括这两个点）所构成的矩形的和，则

res = sum[k][l] - sum[i - 1][l] - sum[k][j - 1] + sum[i - 1][j - 1]

差分

一阶差分的简单应用：

• 快速区间加同一个数。
• 求要使得原序列所有数相等，需要进行至少多少次差分，最后得到的序列有几种结果。最少差分数可以通过配对 + 单独处理剩余部分计算，结果数只要在单独处理部分的次数 + 1即可。

高阶差分的性质：

可以对一个数列不断地做差分。倘若一个数列的通项是多项式的话，那么差分到一定阶数之后，差分序列会全部变成0。对于以$p$次多项式为通项的数列，其$p + 1$阶差分序列一定全部都是0。

我们可以把从原数列到其高阶差分排成一个三角形表，由于差分过程中差分序列的第一项不断后移，所以三角形差分表其实是个“上三角形”。仅由其最左边那一“列”（或者说对角线）也可以确定原数列，方法就是求前缀和递推，从而可以确定整个差分表。

差分具有线性性质，不加证明。

对于一个差分表来说，假如其第一条对角线是$c_0, c_1, ...c_p, 0, 0, ...$，$c_p \ne0$，那么原序列的通项是多项式，为

$a_n = c_0\tbinom{n}{0} + c_1\tbinom{n}{1} + c_2\tbinom{n}{2} + ... + c_p\tbinom{n}{p}$

由于$c_0$必然是$0$，所以可以省略第0项不写。

要证明这个，可以使用线性性，分别考虑$p + 1$个简单差分表，然后把他们算出来的通项分别加起来，就是这个结果了，具体可以参见组合数学。

上面那个性质也可以用来求和，只要写出第$-1$行，就可以求和了：

$\sum_{k = 1}^na_k = 0\times\tbinom{n + 1}{0} + c_0\tbinom{n + 1}{1} + ... + c_p\tbinom{n + 1}{p}$

高阶差分的应用：

• 求通项是多项式的序列的通项公式
• 求通项时多项式的序列的前缀和公式

（组合数学乱入）

二维差分：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

typedef long long ll;

ll n, m, q, a[N][N], b[N][N];

int main() {
    scanf("%lld%lld%lld", &n, &m, &q);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%lld", &a[i][j]);
            // 构造差分矩阵
            b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
        }
    }

    int x_1, y_1, x_2, y_2, c;
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d%d%d", &x_1, &y_1, &x_2, &y_2, &c);

        // 差分过程，在画图上画一画就知道
        b[x_1][y_1] += c;
        b[x_1][y_2 + 1] -= c;
        b[x_2 + 1][y_1] -= c;
        b[x_2 + 1][y_2 + 1] += c;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 求原矩阵
            b[i][j] += (b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]);
            printf("%lld ", b[i][j]);
        }
        puts("");
    }

    return 0;
}

二分

将最优化问题转化为可行性问题。

由于据说90%的程序员写不对二分，所以先介绍一下二分的代码模板：

投机版二分

实现思路是尽可能缩小搜索区间长度，最终将区间长度缩小到不超过2，最后特判端点。

int l = 1, r = n, mid;
while (l + 1 < r) { // 保证最终区间长度不超过2
    mid = (l + r) / 2;
    // 假如是查找一个尽可能大的值
    if (check(a[mid])) {
        l = mid;
    } else {
        r = mid;
    }
}
int ans = (check(a[r]) ? a[r] : a[l]);

这个模板在大部分情况下是没有问题的，且比标准二分模板细节少很多，且最终的边界可以灵活处理。但是有一个毒瘤的交互题113. 特殊排序 - AcWing题库对询问次数的限制卡得非常紧，所以卡掉了这种投机版二分。

但我还是强烈安利这种投机二分的，因为其仅仅牺牲了一点点性能，但却让处理更加简单了。

非投机二分模板之一示例

我们先观察一件事情：

$mid = \frac{l + r}{2}$

由计算机的除法可以知道，这个东西是向0取整，所以，当二分出现负数的时候，使用除法去计算mid可能导致多舍去了一个端点而漏解。解决方案是使用向下取整的算术右移。

$mid = (l + r) >> 1$

再观察一下，这样计算的话，在$l < r$时，$mid < r$必然成立。所以如果循环条件是while (l < r)，那么在改变左端点的时候，一定要l = mid + 1，而右端点的修改只需要r = mid。这样就保证了不会出现死循环。并且，最终一定缩为一个点，则该点就是答案了。

至于check时到底如何定义边界，需要仔细思考。以及，有时候要的最终结果和lower_bound或者upper_bound的行为一致，这个时候更要仔细考虑check的写法。比如，假设求第一个大于等于key的元素位置，那么check时需要保证a[mid] >= x的时候缩右端点；假设求第一个大于key的元素的位置，则check时要保证a[mid] > x时缩右端点。倘若要求小于等于x的最右边的那个位置，如果想直接二分出那个位置，则需要将mid = (l + r + 1) >> 1，且更新的时候l = mid, r = mid - 1；如果要间接求的话可以先求严格大，然后位置-1。总之，在更新区间和check的时候需要非常注意，具体问题具体分析。

所以，还是投机版二分香啊，不管求啥，循环条件和端点更新都是统一的，只要专心设计check即可，最终的边界只需要调用check函数来判断。

实现lower_bound与upper_bound

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int a[N], n, q;

// 找到升序序列中第一个大于等于x的数的下标，没有则返回-1
int get_low(int x) {
    int l = 0, r = n - 1, mid;

    while (l + 1 < r) {
        mid = (l + r) / 2;
        if (x == a[mid]) {
            r = mid;
        } else if (x < a[mid]) {
            r = mid;
        } else {
            l = mid;
        }
    }

    if (a[l] == x) return l;
    else if (a[r] == x) return r;
    else return -1;
}

// 找到升序序列中第一个大于x的数的下标，没有则返回-1
int get_high(int x) {
    int l = 0, r = n - 1, mid;

    while (l + 1 < r) {
        mid = (l + r) / 2;
        if (x == a[mid]) {
            l = mid;
        } else if (x < a[mid]) {
            r = mid;
        } else {
            l = mid;
        }
    }

    if (a[r] == x) return r;
    else if (a[l] == x) return l;
    else return -1;
}

int main() {
    cin >> n >> q;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int x;
    for (int i = 1; i <= q; i++) {
        cin >> x;
        int st = get_low(x);
        int ed = get_high(x);

        cout << st << " " << ed << endl;
    }

    return 0;
}

STL lower_bound()与upper_bound()的使用

首先，在不做任何特殊操作的情况下，这两个函数都是在升序容器中做的。

如果是从下标 1 开始用数组，那么在升序数组 a[] 中查找 key 的用法是 int pos = lower_bound(a + 1, a + n + 1, key) - a

如果是使用容器，那么在升序存储容器 a 中查找 key 的用法是 int pos = lower_bound(a.begin(), a.end(), key) - a.begin()

如果是降序数组，从下标 1 开始使用，那么使用 lower_bound 返回第一个小于等于 key 的元素的位置应该使用 int pos = lower_bound(a + 1, a + n + 1, key, greater<int>()) 。这里假设元素是 int 类型。在降序数组中， upper_bound 是求第一个小于该元素的位置。

对于没有定义顺序的类型，可以通过重载 < 实现顺序的定义，或者在使用二分函数之前写一个 cmp 比较函数，这个比较函数可以定义“有序” 的概念。

二分答案的应用场景

这里介绍一下二分的一个常用的场景：二分答案。

什么时候可以二分答案呢？一般是我们想要求一个答案，这个答案在某个区间内，我们每次可以确定在左半边区间或者右半边区间一定可以找到一个合法的答案，所以每次操作都可以把搜索区间二分掉。

另外一种情况是，我们每次取区间中点，判断一下中点处是不是一个可行解，如果满足题意，利用单调性，往一边搜，否则往另一边搜。这种思路的二分答案关键在于如何快速判断中点处是不是一个可行解，这个有时候只需要简单的贪心，有的时候则不容易找到这么一种判定方法，这样就不适合二分答案了。

我们举一个不是很容易理解的应用例子：113. 特殊排序 - AcWing题库

这个顺序关系不具有传递性，只是具有反对称性，并且保证了我们的数组中没有重复元素。

我们可以先思考一下这个排序如何暴力去做：

• 首先询问两个数，其大小关系一定能排出来，所以能确定顺序。
• 询问第三个数和当前数列中最左边的数
  • 如果小于最左边的数，就放到最左边
  • 否则，和最右边的数比较
    • 如果大于最右边的数，则放到最右边
    • 否则，这个数小于最右边的数，大于最左边的数，那么我们从右往左去看，肯定是可以找到一个空位，使得这个数比左边大且比右边小的。为什么呢？我们可以研究一下这个数从最右边往左一个一个看，可能遇到哪些情况：
      • 比左边大，比右边小，bingo
      • 比左边大，比右边大，但是我们是一路比右边小着比下来的，所以不可能遇到比右边大的情况，不然早就找到答案了，即答案在右边
      • 比左边小，比右边小，很好，再往后看就好了，如果遇到大的就爽了，如果没遇到大的，那他也比最左边的大，所以肯定能找到答案，答案在左边
      • 比左边小，比右边大，我们可是一路小着比下来的，不可能遇到比左边小比右边大的情况，不然早就找到答案了，答案应该在右边

分析完了之后，可以发现，我们不用担心找到一个数之后，找不到插入的地方。注意到我们如果把刚才的几个特殊情况（放在两边）考虑进来的话，会发现假如我们知道手里的元素和已经排好序的序列中某个元素的大小，那么我们一定能够确定在某一边能找到合适的插入位置。所以这样的话就可以直接二分了。

参考代码如下：

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        
        for (int i = 1; i <= N; i++) {
            res.push_back(i);
        }
        for (int i = 1; i < N; i++) {
            int l = 0, r = i, mid;
            while (l + 1 < r) {
                mid = (l + r) / 2;
                if (compare(res[i], res[mid])) {
                    r = mid;
                } else {
                    l = mid;
                }
            }
            int pos = compare(res[i], res[l]) ? l : r;
            for (int j = i; j > pos; j--) {
                swap(res[j], res[j - 1]);
            }
        }
        
        return res;
    }
};

三分

其作用是求单峰（谷）函数的极值点。

以单峰的有极大值的函数为例子，我们考虑把区间 [l, r] 分成 [l, mid] 和 [mid, r] ，并分别取二者区间的中点 lmid = (l + mid) / 2 ，rmid = (mid + r) / 2 ，之后分情况讨论：

• 假如说 f(lmid) = f(rmid) ，说明 lmid 和 rmid 应该是跨极值点的，这个时候我们令 l = lmid ， r = rmid 即可有效缩小范围。
• 假如 f(lmid) < f(rmid)，那么一定有 lmid 是在极值点的左边的，这个时候我们令 l = lmid
• 假如 f(lmid) > f(rmid) ，那么一定有 rmid 是在极值点右边，所以这个时候我们令 r = rmid

一直这样做下去，就找到极值点了。

使用三分最难地方在于发现函数是单峰函数，不能随便口胡和意淫。

下面给一个代码模板（基于洛谷三分法模板）：

#include <bits/stdc++.h>

using namespace std;

const int N = 15;
const double eps = 1e-6;

double l, r, a[N];
int n;

// 这里使用的是多项式函数，题目数据保证[l, r]上是单峰的且有极大值
double f(double x) {
	double res = 0, base = 1;
	for (int i = n + 1; i > 0; i--) {
		res += (a[i] * base);
		base *= x;
	}
	return res;
}

int main() {
	cin >> n >> l >> r;

	for (int i = 1; i <= n + 1; i++) {
		cin >> a[i];
	}

	while (fabs(r - l) > eps) {
		double mid = (l + r) / 2, lmid = (l + mid) / 2, rmid = (mid + r) / 2;
		double flmid = f(lmid), frmid = f(rmid);
		if (flmid == frmid) {
			l = lmid;
			r = rmid;
		} else if (flmid < frmid) {
			l = lmid;
		} else {
			r = rmid;
		}
	}

	cout << l << endl;

	return 0;
}

排序

快排

个人认为快排是主流排序方法中最容易写错的一个了。

快排的基本原理不讲了，下面说一些需要注意的边界情况，并介绍一个非常好写（但是和市面上常见的快排不太一样）的快排模板。

首先，明确我们的函数的作用：quick_sort(arr, l, r)的作用是，使得arr[]的l到r是有序的（感觉像是说了句废话）。

然后，思考一下如何做的划分。这里采取的划分方式是取一个中介元key，然后使得小于key的所有元素肯定全部在左边那段，大于key的所有元素全部在右边那段（思考这句话与左边那段全是小于key的元素，右边那段全是大于key的元素的不同）。可以看到，这样做就是把数组划分成两段了，可能失去了传统快排中一轮下来肯定能确定至少一个数的位置的性质。

比如，考虑下面的样例：

5 2 10 7 9 0 8

以数字$5$作为中介元，那么$5$到底能不能在本轮排序中到达自己的最终位置完全取决于我们如何处理的边界。假如我们处理的方式是这样的：

int i = l - 1, j = r + 1, key = 5;
while (i < j) {
    do i++; while (a[i] < key);
    do j--; while (a[j] > key);
    if (i < j) swap(a[i], a[j]);
}
quick_sort(a, l, j), quick_sort(a, j + 1, r);

那么第一轮排序之后，结果是这样的：

0 -2 j- -10 i- 7 9 5 8

显然$5$没有在最终位置，但是小于key的元素确实全部到了j及其左边，大于key的元素确实全部到了j的右边，因为最终i停下时a[i] >= key，j最后停下时a[j] <= key，所以以j为分界线分治是合理的。

细心的朋友们可能发现，上述实现根本没考虑i, j越界的情况，但不久之后我们会惊奇地发现确实不需要考虑这一点。不妨假设i可以无限i++，那么说明i从某个时间开始扫到的元素全部都满足a[i] < key的情况，但仔细思考我们会发现，右边至少会有一个大小为key的元素存在，否则，我们就选了一个不存在于这一段中的中介元，所以i一定会停下，并且最终停下的时候必然不满足i < j（因为如果i < j，那么可以做一次交换，i后面自增的时候会碰到刚才交换之后的元素的）。j--同理可以证明。

对于边界情况，假设只有一个元素的话，即l == r，那么其分治下去会划分成quick_sort(arr, l ,l)和quick_sort(arr, l + 1, l)，为了避免这种情况，我们在l >= r的时候让其退出即可。

另外对于中介元的选取，为了防卡可以随机取，偷懒可以取中点。

综上， 我们就得到了一个看起来有点奇怪但是却格外好写（指细节少 + 好记）的快排板子：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

yxcnb！

这个也可以做第k小的数，定义函数int quick_sort(int q[], int l, int r, int k)，其返回值是数组q的[l, r]下标范围内的第k大的数，算法流程如下：

int quick_sort(int l, int r, int k) {
    if (l == r) return a[l]; // 由于函数的定义，所以[l, r]中第k大的数就是这唯一的数了

    int i = l - 1, j = r + 1, x = a[l];

    while (i < j) {
        while (a[++i] < x);
        while (a[--j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    // 注意这个边界
    if (j - l + 1 < k) {
        return quick_sort(j + 1, r, k - (j - l + 1));
    } else {
        return quick_sort(l, j, k);
    }
}

归并排序

归并排序的思想是把序列二分成更短的序列，当两个更短的序列排序之后，使用较小的代价快速归并。

void merge(int q[], int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;

    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) {
            tmp[k++] = q[i++];
        } else {
            tmp[k++] = q[j++];
        }
    }

    while (i <= mid) {
        tmp[k++] = q[i++];
    }

    while (j <= r) {
        tmp[k++] = q[j++];
    }

    for (i = l; i <= r; i++) {
        q[i] = tmp[i];
    }
}

void merge_sort(int q[], int l, int r) {
    if (l < r) {
        int mid = (l + r) >> 1;
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);
        merge(q, l, mid, r);
    }
}

归并排序的思想可以用来解决形如统计 $i < j$ 且 $f(a[i]) > f(a[j])$ 的问题，当然也可以使用权值树状数组。

堆排序

堆排序需要我们先通过插入法建立堆，然后不断输出并弹出最小值，这样便实现了排序。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int q[N], n, m, sz;

void ins(int x) {
    sz++;
    q[sz] = x;

    for (int i = sz / 2, j = sz; i > 0; i /= 2) {
        if (q[i] > q[j]) {
            swap(q[i], q[j]);
            j = i;
        } else {
            break;
        }
    }
}

int get_top() {
    return q[1];
}

void del() {
    swap(q[1], q[sz]);
    sz--;

    for (int i = 1; i <= sz / 2; ) {
        int j = 2 * i;
        if (j + 1 <= sz && q[j + 1] < q[j]) {
            j++;
        }

        if (q[i] <= q[j]) {
            break;
        } else {
            swap(q[i], q[j]);
            i = j;
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> q[i];
        ins(q[i]);
    }

    for (int i = 1; i <= m; i++) {
        cout << get_top() << " ";
        del();
    }

    return 0;
}

另一种方案是，建立大根堆，然后把所有的元素弹空，最后得到的也是排序后的结果（这个可能依赖于堆的实现，本实现方法是可以的）。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int q[N], n, m, sz;

void ins(int x) {
    sz++;
    q[sz] = x;

    for (int i = sz / 2, j = sz; i > 0; i /= 2) {
        if (q[i] < q[j]) { // 大根堆
            swap(q[i], q[j]);
            j = i;
        } else {
            break;
        }
    }
}

int get_top() {
    return q[1];
}

void del() {
    swap(q[1], q[sz]);
    sz--;

    for (int i = 1; i <= sz / 2; ) {
        int j = 2 * i;
        if (j + 1 <= sz && q[j + 1] > q[j]) {
            j++;
        }

        if (q[i] >= q[j]) {
            break;
        } else {
            swap(q[i], q[j]);
            i = j;
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> q[i];
        ins(q[i]);
    }

    for (int i = 1; i <= n; i++) {
        del(); // 每次把当前堆内最大值放到末尾，所以最后恰好得到升序序列
    }

    for (int i = 1; i <= m; i++) {
        cout << q[i] << " ";
    }

    return 0;
}

中位数

排序之后，我们可以快速求出来中位数是多少。事实上，很多问题用到了中位数的性质，所以值得在这里开一个标题介绍一下。

典型题目：

货仓选址，最裸的考察中位数的性质的题目。不熟悉这个性质的可以证明一下，然后过了这个题。

均分纸牌，可以通过对绝对值方程组进行推导，得到答案式子，然后发现考察的就是中位数的这个性质。

糖果传递，上一道题目的环形版本。

七夕祭，上上个题的环形+二维版本。

完美矩阵，发现矩阵中相关联的需要相等的数之后，发现其实还是求这几个关联数的中位数

把这几个题目做透彻了，证明部分能自己写出来，就差不多了。

另外还有一些和中位数有关的数据结构问题，比如动态查询中位数，一般化之后可以是动态查询第$k$​大的问题，可以通过对顶堆来维护。

下面给出二维环形糖果传递的解题报告：

对于每行，假设有 $x_i$ 个糖果，总糖果为 $s$，一共有 $n$ 行，那么每行需要调整成 $\frac{s}{n}$​ 个糖果才可以，不妨记成 $avg$。我们假设，第 $i$ 行应该给 $i - 1$ 行 $c_i$ 个糖果，则：

$\begin{cases} x_1 - c_1 + c_2 = avg\\ x_2 - c_2 + c_3 = avg\\ ...\\ x_n - c_n + c_1 = avg \end{cases}$

注意到这是 $n$ 个方程，存在 $n$ 个未知数，分别是 $c_i$ ，并且发现把所有的方程加起来会得到 $0 = 0$ ，所以系数矩阵不满秩，事实上是 $n - 1$ 。我们考虑用 $c_1$ 表示其他的 $c_i$，会发现：

$\begin{cases} c_1 = c_1\\ c_2 = avg - x_1 + c_1\\ c_3 = avg - x_2 + c_2 = avg - x_2 + avg - x_1 + c_1 = 2avg - x_1 - x_2 + c_1\\ ...\\ c_{n} = (n - 1)avg - (x_1 + ... + x_{n - 1}) + c_1 \end{cases}$

我们希望的是使得 $|c_1| + |c_2| + ... + |c_n|$​ 最小，所以就是让下面的式子最小：

$|c_1| + |c_1 + avg - x_1| + |c_1 + 2avg - x_1 - x_2| + ... + |c_1 + (n - 1)avg - (x_1 + x_2 + ... + x_{n - 1})|$

可以看出来，变量只有 $c_1$​ ，所以只要让 $c_1$​ 等于数列 $\{\sum_{i = 1}^{k}x_i - kavg\}$​​​ 的中位数即可，然后求出所有的差的绝对值，求和即可。

STL sort()的使用

对于已经定义了顺序的类型排序，如果是升序排序，那么直接 sort(a.begin(), a.end()) 即可。如果降序，则可以调用 greater<int>() 这个已经写好的排序函数或者自定义 cmp 函数，使用sort(a.begin(), a.end(), cmp)。

对于未定义顺序的类型，可以使用 cmp 自定义比较函数，或者重载 < 。

倍增

倍增的主要思路是，如果信息不具有上述性质，那么查询的时候就只能老老实实地拆分成正交的几个区间来做了，这样复杂度能做到$O(\log n)$。一般来说，我们使用ST表的时候都是解决可重复贡献问题（RMQ，区间GCD，区间），其他的问题我们一般使用其他的数据结构去做，而在倍增LCA中，我们则是使用的后面说的拆分成多个区间去查询的方法。

倍增算是一个使用的比较普遍的技巧了，比如在求LCA的时候一种算法就是倍增LCA，在RMQ问题中的ST表算法的主要思路也是倍增，下面就拿这两个介绍一下倍增。

ST表（Sparse Table）

ST表（稀疏表）可以用来解决静态区间查询最值的问题，也可以做区间或，区间与以及区间GCD等可重复贡献问题，以$O(n\log n)$的时间预处理，每次只要$O(1)$询问（RMQ），当询问特别多但是$n$特别小的时候，线段树这种会被卡，但是ST表则可以高效运行。下面以RMQ为例子详细说一下。

ST表要求我们预处理出这样的信息：对所有的1 <= i <= n，预处理出[i, i + 2^j - 1]的RMQ，然后查询的时候，把待查询区间[l, r]拆分成[l, l + 2^s - 1]以及[r - 2^s + 1, r]这样的两个区间，然后直接拿这两个区间的结果合并一下就好了。这里的s可以取log(r - l + 1)，因为r = l的时候不能算lg[0]。

在实现预处理的时候，我们会开一个二维数组st，以st[i][j]表示[i, i + 2^j - 1]的信息，注意递推的时候递推公式是st[i][j] = merge(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])，所以应该初始化所有的st[i][0]，并且先从小到大枚举j，然后再枚举i。在查询的时候，由于对数计算需要时间，所以可以预处理的时候就把对数预处理出来。

求静态区间最大的代码模板如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 200020;

int st[N][22], n, m, a[N];
int lg[N];

int main() {
    int l, r;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        st[i][0] = a[i];
    }

    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i / 2] + 1; 
    }
    for (int j = 1; j <= lg[n]; j++) {
        for (int i = 1; i <= n; i++) {
            if (i + (1 << j) - 1 > n) break;
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &l, &r);
        int s = lg[r - l + 1];
        printf("%d\n", max(st[l][s], st[r - (1 << s) + 1][s]));
    }
    return 0;
}

还有一个值得注意的地方：st[N][M]数组中，上述实现中第二维远小于第一维，所以为了减少cache miss，可以把两维互换。

倍增LCA

倍增也可以用来快速求LCA。

基本思路和ST表差不多：对于每个点，预处理其2^j级祖先（所以需要记录一下深度），可以采用fa[i][j] = fa[fa[i][j - 1]][j - 1]递推；在查询的时候，先倍增跳，让两个点深度一样，再倍增往上跳，最终求出结果。可以看出这样做的单次查询复杂度是$O(\log n)$的，这个问题也展示了倍增时没有可重复贡献性质的问题的区间如何进行拆分。

代码模板如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 40040, M = 2 * N;

int h[N], e[M], ne[M], idx;
int n, m, root;
int lg[N], fa[N][20], d[N];

void add(int x, int y) {
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

void dfs(int u, int f, int depth) {
    d[u] = depth;
    fa[u][0] = f;
    for (int i = 1; i <= lg[depth]; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    
    for (int i = h[u]; i >= 0; i = ne[i]) {
        if (e[i] != f) {
            dfs(e[i], u, depth + 1);
        }
    }
}

int lca(int x, int y) {
    if (d[x] < d[y]) {
        return lca(y, x);
    }
    
    while (d[x] > d[y]) {
        x = fa[x][lg[d[x] - d[y]]];
    }
    
    if (x == y) {
        return x;
    }

    for (int i = lg[d[x]]; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    
    return fa[x][0];
}


int main() {
    scanf("%d", &n);
    
    memset(h, -1, sizeof h);
    int x, y;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        if (y == -1) {
            root = x;
        } else {
            add(x, y);
            add(y, x);
        }
    }
    
    for (int i = 2; i < N; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    
    dfs(root, 0, 1);
    
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        int z = lca(x, y);
        if (z == x) {
            puts("1");
        } else if (z == y) {
            puts("2");
        } else {
            puts("0");
        }
    }
    
    return 0;
}

贪心

个人认为贪心是最难的一种问题了，一方面，我们得发现这个题可以贪心，另一方面，我们还得有把握去说明刚才谈到的贪心是正确的。

学习贪心，有时候需要理论推导发现贪心策略，有时候需要大胆猜想 + 小心求证。总而言之，严谨的理论推导是必要的。

贪心解的证明

证明贪心算法的正确性可以使用以下方法：

任给一个最优解$ans2$，现在手里有一个贪心解$ans1$，证明$ans1 \geq ans2$，且$ans2 \geq ans1$，即证明将最优解调整成贪心解，且解不会变坏。

几个具体例子

下面列举几个贪心的例子，主要阐述如何发现贪心策略和如何证明正确性。
125. 耍杂技的牛 - AcWing题库

有一群牛，每头牛有重量和强壮度两个属性。现在把这些牛全部摞成一个塔，对于每头牛来说，它的危险系数是其上面的所有牛的重量（不包括自己）减去自己的强壮度。现在想让整个塔的最大的危险系数最小，问如何安排牛的摞法？

本题干想是想不出来什么贪心策略的，但感觉上就是一个贪心的问题，这个时候需要使用一些贪心中常用的套路去尝试一下是否存在贪心策略。

在这里，我使用了邻位交换法。邻位交换法的一般步骤如下：

• 考虑某个决策序列，考虑其中任意一对相邻的决策$i$和$i + 1$
• 分别考虑当决策顺序为$i,i+1$和$i+1,i$时，会得到怎么样的结果
• 对于这两种结果，不妨强行令一个结果优于另一个结果，看看需要怎样的原因才能导致这个结果
• 如果我们发现了某种原因，导致一个结果能够优于另一个结果，那么我们就可以使用这个原因去把一个决策序列优化到无法再用这种方式去优化。
• 如果没有其他类型的优化方法，那么当前就得到了最优解。对于一般的贪心题目来说，上面找到的那个原因，基本就能够得到最优解了。

我考虑了前$i+1$头牛，对于第$i$头和第$i+1$头牛，研究二者的不同摞法会导致怎样的结果：

• 如果$i$放在$i + 1$上面，那么$i$的危险程度就是$sumw - s[i]$，$i + 1$的危险程度就是$sumw + w[i] - s[i + 1]$
• 如果$i + 1$放在$i$上面，那么$i + 1$的危险系数就是$sumw - s[i + 1]$，$i$的危险系数就是$sumw + w[i + 1] - s[i]$

我们讨论一下这两个结果分别的最大值之间的关系，即讨论$max(sumw - s[i],sumw + w[i] - s[i + 1])$和$max(sumw - s[i + 1], sumw + w[i + 1] - s[i])$，倘若第一个式子大于等于第二个式子，那么应该是什么情况呢？分类讨论一下左边的式子的最大值：

• 倘若左边式子的最大值为$sumw - s[i]$，那么就有$sumw - s[i] \geq max(sumw - s[i + 1], sumw + w[i + 1] - s[i])$，但是很显然，不等号左边的式子必然小于右边的$max$中的第二项，所以这种情况不会存在。
• 倘若左边式子的最大值为$sumw + w[i] - s[i + 1]$，那么就有$sumw + w[i] - s[i + 1] \geq max(sumw - s[i + 1], sumw + w[i + 1] - s[i])$ 。那么从这个不等式中还能得到什么东西呢？我们不妨分类研究一下右边的$max$
  • 倘若右边的$max$为$sumw - s[i + 1]$，那么就要有$w[i] - s[i + 1] \geq -s[i + 1]$，发现纯属废话
  • 倘若右边的$max$为$sumw - w[i + 1] - s[i]$，那么就要有$w[i] - s[i + 1] \geq w[i + 1] - s[i]$，整理一下就是$w[i] + s[i] \geq w[i + 1] + s[i + 1]$。

至此，我们分类讨论了一个结果优于另一个结果的所有情况。除去非法情况，我们发现合法情况中，只要满足$w[i] + s[i] \geq w[i + 1] + s[i + 1]$，那么就有$i$放在$i + 1$上面之后这两个的最大危险大于$i + 1$放在$i$上面的最大危险。所以，如果按照$w[i] + s[i]$升序排序，然后按照这个顺序从上到下摞起来奶牛，那么就可以得到一个“很好的结果”。至此，我们发现了贪心的策略。

问题解决了吗？似乎是没有的。在$w[i] + s[i]$的优化上，我们已经做到了极限，那么到底还有没有其他的策略能够得到比这种贪心解还要好的结果呢？下面的过程就是证明贪心解确实是最优解。对于其他任何一种解，假如其存在不满足贪心策略的选择，那么我们可以将其进行交换，前面已经证明了，这样做不会让解更差，所以对于其他最优解来说，一定可以转化成贪心解。所以，贪心解确实是最优解之一。到这里，这个问题就真的做完了。

110. 防晒 - AcWing题库

有一群奶牛，每头奶牛需要接受$[a_i,b_i]$的阳光，有一些化妆品，奶牛涂上某种化妆品之后，会稳定的接受到一定的阳光，问最多能够满足多少奶牛接受适当的阳光。

这个题目看起来很像二分图的最大匹配问题，并且通过将奶牛和化妆品之间建立边之后确实可以使用匹配算法去做，但是复杂度似乎是吃不消的，我们得想其他的办法。

我事先知道这是一个贪心题了，很遗憾，所以我直接猜应该怎么贪心。我想的是，有些化妆品可能比较少，并且这种化妆品所能满足的奶牛，其他数量比较多的化妆品可能也可以满足。倘若奶牛都被比较多的化妆品满足了，那么数量比较少的化妆品就没法用出去了，所以看起来似乎应该优先考虑使用数量比较少的化妆品。但是下面这组数据可以hack掉这种思路：

3 3
9 12
5 20
5 20
5 1
11 1
12 1

倘若先分配5，那很好；倘若先分配的11（确实有这种可能，因为他们都是最少的），11分配给了5-20的奶牛，那么5的化妆品就废掉了。

那应该怎么贪心呢？这个问题的贪心策略其实是：将奶牛按照$minspf$降序排序，将化妆品按照$spf$降序排序，然后就会出现这样的性质：如果化妆品$i$大于当前的奶牛的$minspf$，那么该化妆品就大于剩下所有的奶牛的$minspf$，且$i -1$化妆品也大于剩下的。对于剩下的所有奶牛，对于$i - 1$和$i$这两种化妆品，要么这两个都能满足某个奶牛，要么都不能满足，要么$i$能够满足但$i - 1$不能满足。所以，使用一个指针扫描奶牛，另一个指针扫描化妆品，找到第一个可以的化妆品就好了，这样就不会出现原本可以充分利用某种化妆品但是因为别人占用而浪费的情况了。

双指针

做到提高组之后,很多oier仅仅是觉得好像有这么一个两个指针从左到右扫一遍的算法存在,却不知道它的名字.(其实是因为大佬们根本没把它当个算法) ——某大佬

双指针算法主要用来解决具有单调性的问题。说起单调性，二分也可能可以解决答案具有单调性的问题。有些题目使用双指针或者二分都是可以做的。除了单独解决问题，这个算法经常用来优化一些别的算法的某些计算过程~~（这种基础算法用起来就是妙呀）~~。

注意，双指针和单调栈、单调队列不是一类东西，各自解决的问题也不一样（虽然名字和形式上有点像）：

• 双指针相比于单调队列
  • 双指针维护的是左右两个指针之间的区间的一个属性，不一定是最值。并且，双指针的限制不一定是滑动窗口的最大长度，而是一个性质是否满足，长度可能只是我们关心的一个性质（甚至可能完全不关心）。
  • 而单调队列的作用很局限，就是维护滑动窗口最值。为了高效维护最值，需要支持队列尾部的插入删除元素，头部始终是最值。
• 双指针相比于单调栈
  • 单调栈的作用也很局限，它是用来求一个序列中每个元素左边或右边第一个比自己大或者小的元素位置的。
  • 双指针，显然和这个不一样。

基本步骤

常见双指针的基本步骤是：

确定指针的含义，确定单调性（第一个指针往后走的时候，第二个指针是否是单调移动的）。

在实现时，维护两个指针l，r，初始都从起点开始，让r不断向后移动，当l和r之间满足（不满足）一定条件之后不断向后移动l直到破除上述条件，不断执行上述流程，直到r指针走到序列末尾。

用代码描述大概是这样的：

// i是右端点，j是左端点
for (int i = 1, j = 1; i <= n; i++) {
    while (j < i && check(i, j)) j++;

    // 具体问题的逻辑
}

看了代码模板，发现这个算法其实就是在维护一个普通的队列，怪不得dalao们没把它当作是算法。

另一种风格的双指针是两个指针分别维护两个序列，移动策略是始终使得两个序列满足某个关系，这就不是维护队列了，而是有归并排序内味儿。

光说基本步骤看起来也过于简单了，光讲步骤也想象不出来这个玩意儿可以用来做什么事情，所以重点还是看下面的题目。

应用举例

先看几个俩指针维护同一个序列的问题：

• 有一个正整数序列，求区间和大于等于$S$的最短区间的长度。

  容易发现，如果长度不超过len的区间可以，那么长度不超过len + 1的区间也可以；如果长度不超过len的区间不可以，那么长度不超过len - 1的区间也不可以。所以，这个题可以直接二分区间的长度，然后枚举前缀和的右端点，算一下左端点是不是可以，这样的复杂度是$O(n\log n)$。

  另外还有一种二分思路：枚举区间右端点，二分出来最大的区间左端点。

  emmm但是这好像是个双指针的入门题目，一般数据范围都会给到1e7以上，二分就不可以做了。

  双指针做这个题的方法是这样的：指针l，r分别最开始置于起点，然后移动r，当l到r的区间和大于$S$的时候，就不先移动r了，改成移动l，直到区间和小于$S$，然后再移动r指针，不断进行这个过程，直到r到达尾端，可以看到两个指针加起来最多移动$2n$，所以复杂度$O(n)$。从这里能看出来双指针的复杂度有种均摊的味道，不会因为某次操作复杂度高导致整体复杂度高。

  这个过程中枚举的区间中满足和大于等于$S$最短的那个就是答案了。能看出来这个过程也是在枚举，但是效率却很高。和第二种二分思路对比一下，能发现它们的思路都是枚举右端点，然后尽可能快地找到最靠右的左端点，只不过二分是使用二分法做的，双指针是持续维护的左指针l。这样一看是不是有点感觉了？

• 给一个序列，这个序列中有$n$个数，这$n$个数是$m$种数。求一个最短区间，使得这个区间里出现了这$m$种数至少一次，返回区间长度即可。

  这种题面比较简单的题目，一眼看过去一般能想到很多种做法。比如考虑一下上一个题目的思路，枚举右端点，二分一个最靠右的满足条件的左端点，复杂度$O(nm\log n)$，多一个$m$是因为这个题目和上一个题目的最大不同点在于需要维护类似$m$种不同的前缀和。$n,m$有一个比较大的时候这个方法就无了。

  考虑一个双指针的搞法，当区间符合要求的时候不断右移左端点，每移动一次只要$O(1)$的时间去更新结果，所以复杂度也是$O(n)$的。

• 求一个序列中没有重复数字的最长区间

  如果告诉大家使用双指针做，那会发现这和上一个题基本一样。唯一要关心的是，数字可能比较大，想快速维护每个数字出现了几次以及空间开的不是特别离谱的话，可能要离散化或者map。

• 给一个正整数序列，求满足条件的区间[l, r]的对数。条件是a[l] ^ a[l + 1] ^ ... a[r] = a[l] + a[l + 1] + ... + a[r]。

  考虑到异或的本质是不进位加法。当异或结果和加法结果相同的时候，意味着涉及到的这些数里面每个二进制位都至多有一个为1，否则一定是左边比右边小，欸这个题的单调性和上一个题又有点像了。移动r的时候，如果当前异或和不等于普通和，则右移左指针，直到相等，这就是移动策略了。

再看几个双指针维护两个序列的问题。这种问题的原型可以想一下双指针在归并排序中的应用。

• 给一个整数序列，求有多少个区间的和小于$t$

  这个应该不难转化为求$sum[r] - t< sum[l - 1]$的$(l, r)$的对数，可以枚举$r$，然后想办法快速搞出来$l$的个数，欸，突然就想到了前几天深入理解了一下很适合统计这种"逆序对"的值域树状数组，所以这里直接上树状数组就可以快速统计了。

  说起逆序对，归并排序也能做，而归并排序之所以高效，很大原因在于可以通过双指针维护两个序列快速合并，所以这个题目一定程度上说也可以使用双指针来做。

• 给两个升序序列a[]和b[]和一个整数x，求一对(i, j)，使得a[i] + b[j] = x，保证有唯一解。

  使用双指针时，可以把一个指针放到a[]的头部，另一个放到b[]的尾部，然后根据需要移动相应指针就好了。

高精度

主要是积累模板。

高精度加法

高精度加法使用vector十分容易实现：

注意使用reverse(a.begin(), a.end())在必要的时候进行翻转。

#include <bits/stdc++.h>

using namespace std;

vector<int> a, b, c;

vector<int> read() {
    char ch = getchar();
    vector<int> res;
    while (ch < '0' || ch > '9') {
        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        res.push_back(ch - '0');
        ch = getchar();
    }

    return res;
}

vector<int> add(vector<int> a, vector<int> b) {
    if (a.size() < b.size()) {
        return add(b, a);
    }
    vector<int> res;

    int t = 0;
    for (int i = 0; i < (int) a.size(); i++) {
        t += a[i];
        if (i < b.size()) {
            t += b[i];
        }
        res.push_back(t % 10);
        t /= 10;
    }

    if (t) res.push_back(t);

    return res;
}

void print(vector<int> a) {
    for (int i = a.size() - 1; i >= 0; i--) {
        printf("%d", a[i]);
    }
}

int main() {
    a = read();
    b = read();
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    c = add(a, b);
    print(c);
    return 0;
}

高精度减法

使用大数减小数，不是的话则交换一下然后结果取相反数。

#include <bits/stdc++.h>

using namespace std;

vector<int> a, b, c;

int cmp(vector<int> a, vector<int> b) {
    if (a.size() == b.size()) {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] != b[i]) {
                return a[i] - b[i];
            }
        }
        return 0;
    } else {
        if (a.size() < b.size()) {
            return -1;
        } else {
            return 1;
        }
    }
}

vector<int> read() {
    char ch = getchar();
    vector<int> res;
    while (ch < '0' || ch > '9') {
        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        res.push_back(ch - '0');
        ch = getchar();
    }
    
    reverse(res.begin(), res.end());

    return res;
}

vector<int> sub(vector<int> a, vector<int> b) {
    vector<int> res;
    if (cmp(a, b) < 0) {
        res = sub(b, a);
        res[res.size() - 1] *= -1;
        return res;
    }
    
    int t = 0;
    for (int i = 0; i < a.size(); i++) {
        t = a[i] - t;
        if (i < b.size()) {
            t = t - b[i];
        }
        res.push_back((t + 10) % 10);
        if (t < 0) {
            t = 1;
        } else {
            t = 0;
        }
    }
    
    while (res.back() == 0 && res.size() > 1) {
        res.pop_back();
    }
    
    return res;
}

void print(vector<int> a) {
    for (int i = a.size() - 1; i >= 0; i--) {
        printf("%d", a[i]);
    }
}

int main() {
    a = read();
    b = read();
    c = sub(a, b);
    print(c);
    return 0;
}

高精度乘法

记录高精度乘以单精度，因为这个比较常用。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

char s[N];

vector<LL> mul(vector<LL> a, LL b) {
    vector<LL> res;
    LL t = 0;
    for (int i = 0; i < a.size(); i++) {
        t += a[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        res.push_back(t % 10);
        t /= 10;
    }
    return res;
}

int main() {
    LL b;
    scanf("%s %lld", s, &b);
    int len = strlen(s);
    vector<LL> a;
    for (int i = len - 1; i >= 0; i--) {
        a.push_back(s[i] - '0');
    }
    a = mul(a, b);
    int pos = -1;
    for (int i = a.size() - 1; i >= 0; i--) {
        if (a[i] == 0) continue;
        pos = i;
        break;
    }
    if (pos == -1) {
        puts("0");
    } else {
        for (int i = pos; i >= 0; i--) {
            printf("%lld", a[i]);
        }
    }
    return 0;
}

高精度除法

记录高精度乘以单精度，因为这个比较常用。（说实话高精度除法不常用）

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

char s[N];

void divide(vector<LL> a, LL b) {
    vector<LL> res;

    LL t = 0, pos = 0;
    bool flag = false;
    for (int i = 0; i < a.size(); i++) {
        t = 10 * t + a[i];
        if (t >= b) {
            flag = true;
            pos = i;
            break;
        }
    }

    if (!flag) {
        printf("0\n%lld\n", t);
        return;
    }

    t /= 10;
    for (int i = pos; i < a.size(); i++) {
        t = 10 * t + a[i];
        res.push_back(t / b);
        t %= b;
    }

    for (int i = 0; i < res.size(); i++) {
        printf("%lld", res[i]);
    }

    printf("\n%lld\n", t);
}

int main() {
    LL b;
    cin >> s >> b;
    vector<LL> a;
    for (int i = 0; s[i] != '\0'; i++) {
        a.push_back(s[i] - '0');
    }

    divide(a, b);

    return 0;
}

高精度压位

目的是优化时间常数。

压位的思路是，让每一个位存储好几位十进制数，这样做计算的时候就能少一些计算次数。

实现一个十进制位存储好几位数的方法就是修改模数，比如模 $1e4$ ，那么每个十进制位存储的就是三位数，这样计算起来常数就会比较小。

离散化

当元素的值域很大，但是实际个数远小于值域中不同元素的个数，且我们只关心元素之间的相对大小的时候，可以使用离散化技术节省存储空间，使得某些问题变得可做。

离散化分为离线离散化和在线离散化。

离线离散化是读入所有数据之后，排序去重得到每个数字离散化之后的结果，然后通过二分去查找每个元素离散化的结果。

在线离散化可以基于 STL 容器，比如 unordered_map，每读入一个元素，就看看是否存在，存在的话就不管了，不存在就插进去，这样也实现了离散化，并且可以边离散化边做其他操作，时间复杂度上也略有优势，但常数上未必优秀。

区间合并

给定一系列区间，求这些区间取并集之后的一系列区间。

可以按照第一关键字左端点，第二关键字右端点排序，然后贪心合并即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

typedef struct {
    int l, r;
} Seg;

int n;
Seg seg[N];
vector<Seg> ans;

bool operator <(const Seg &p, const Seg &q) {
    if (p.l == q.l) {
        return p.r < q.r;
    }
    return p.l < q.l;
}

int main() {
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &seg[i].l, &seg[i].r);
    }
    
    sort(seg + 1, seg + n + 1);
    
    ans.push_back(seg[1]);
    int cnt = 1;
    for (int i = 2; i <= n; i++) {
        if (seg[i].l <= ans[cnt - 1].r) {
            ans[cnt - 1].r = max(seg[i].r, ans[cnt - 1].r);
        } else {
            cnt++;
            ans.push_back(seg[i]);
        }
    }
    
    printf("%d\n", cnt);
    
    return 0;
}

杂项

• a / b 的上取整结果：(a + b - 1) / b
• 枚举一对，不如改成枚举一个，然后快速求出另一个
• 需要分情况讨论，考虑是否可以通过一些变化，使得始终是某种情况成立，而不需要考虑另一种情况