5 篇
记录 ACM 竞赛模式下的排序、前缀和、差分、离散化与区间处理等基础算法。
归并排序的步骤 归并 扫尾 回归 #include <iostream> using namespace std; typedef long long LL; const int N = 100010; int n; int q[N]; int tmp[N]; LL merge_sort(int l,
以下公式均采用从 $1$ 开始的下标，并约定所有下标为 $0$ 的位置值为 $0$。 一维前缀和 对于原数组 $a$，定义前缀和数组 $S$： $$ S_i = \sum_{k=1}^{i} a_k, \qquad S_0 = 0 $$ 递推公式为： $$ S_i = S_{i-1} + a_i $$ 区间 $[L,R
离散化 当一个数组的坐标范围特别大的时候，我们可以用离散化来缩小。 数组去重 vector<int> alls; sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); 定义查找函数 这里使
核心思路 合并区间的关键是：先按照左端点排序，再从左到右维护当前正在合并的区间 $[st, ed]$。 设下一个区间为 $[l,r]$： 如果 $l > ed$，说明它与当前区间没有交集。将 $[st,ed]$ 加入答案，并从 $[l,r]$ 开始维护新区间。 如果 $l \le ed$，说明两个区间有交集，将当前右
#include <iostream> using namespace std; const int N = 100010; int n; int q[N]; void quick_sort(int l, int r) { if (l >= r) return; int i = l - 1, j
