【算法模版】基础算法

快速排序算法模板

快速排序是一种常用的排序算法，它采用分治的思想，通过将数组分为两部分，分别对左右两部分进行排序，从而达到整体有序的目的。

1. 算法原理：
   • 选择数组中的一个元素作为基准（通常选择中间位置的元素）。
   • 将小于基准的元素移到基准的左边，大于基准的元素移到基准的右边。
   • 对基准左边和右边的子数组分别进行递归排序。
2. 算法模板解析：
   • q[] 是待排序的数组，l 和 r 分别表示当前排序的区间左右边界。
   • 使用递归的方式进行排序，当区间长度小于等于 1 时终止递归。
   • 在每一轮排序中，选择中间位置的元素作为基准，即 x = q[l + r >> 1]。
   • 使用双指针法将小于基准的元素放到基准的左边，大于基准的元素放到基准的右边。
   • 递归地对基准左右两边的子数组进行排序。

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);
}

归并排序算法模板

归并排序是一种稳定的排序算法，采用分治的思想，将数组分成两部分，分别对左右两部分进行排序，然后合并两个有序数组。

1. 算法原理：
   • 将数组分成两半，分别对左右两半进行递归排序。
   • 当两个子数组都有序时，将它们合并成一个有序数组。
2. 算法模板解析：
   • q[] 是待排序的数组，l 和 r 分别表示当前排序的区间左右边界。
   • 使用递归的方式进行排序，当区间长度小于等于 1 时终止递归。
   • 将当前区间分成两半，分别进行递归排序。
   • 将两个有序的子数组合并成一个有序数组。

vvoid merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    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, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

整数二分算法模板

整数二分算法用于在有序整数序列中查找满足某种条件的元素，是一种高效的查找算法。

1. 算法原理：
   • 在有序整数序列中，使用二分法确定满足条件的元素的位置。
   • 根据条件判断，调整二分查找的边界，直到找到目标元素或确定不存在目标元素。
2. 算法模板解析：
   • 使用两种不同的二分查找模板，根据不同的条件判断确定边界的调整方式。
   • check 函数用于判断当前位置是否满足条件，具体逻辑由具体问题决定。
   • bsearch_1 用于在区间 [l, r] 中寻找第一个满足条件的元素。
   • bsearch_2 用于在区间 [l, r] 中寻找最后一个满足条件的元素。

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分算法模板

浮点数二分算法用于在浮点数范围内查找满足某种条件的元素，与整数二分算法类似，但需要注意浮点数比较的精度问题。

1. 算法原理：
   • 在浮点数范围内，使用二分法确定满足条件的元素的位置。
   • 根据条件判断，调整二分查找的边界，直到找到目标元素或确定不存在目标元素。
2. 算法模板解析：
   • 由于浮点数比较存在精度问题，需要定义一个足够小的精度值 eps。
   • 在二分查找过程中，当区间长度小于 eps 时终止查找。
   • 使用 check 函数判断当前位置是否满足条件，根据条件判断调整边界。

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度加法、减法、乘法、除法

高精度运算是指对超过计算机表示范围的大整数进行运算，通常使用数组存储大整数，并模拟手工计算的方式进行加减乘除运算。

1. 算法原理：
   • 加法：按位相加，处理进位。
   • 减法：按位相减，处理借位。
   • 乘法：模拟手工乘法，逐位相乘并处理进位。
   • 除法：模拟手工除法，逐位进行除法运算。
2. 算法模板解析：
   • 给出了高精度加法、减法、乘法、除法的模板代码，实现了基本的大整数运算。

高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    
    if (t) C.push_back(t);
    return C;
}

高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘低精度

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

高精度除以低精度

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

前缀和与差分

前缀和与差分是一种常用的数组处理技巧，可以快速求出数组区间和以及快速更新区间元素。

算法原理：

• 前缀和：将数组中每个位置的元素表示为前面所有元素的和，可以快速求出任意区间的和。
• 差分：将原数组中相邻元素的差值存储在另一个数组中，可以快速更新区间内的元素。

算法模板解析：

• 给出了一维前缀和、二维前缀和、一维差分、二维差分的模板代码，详细解释了其原

一维前缀和

一维前缀和是指对数组中每个位置的元素，计算其前面所有元素的和并存储在一个新数组中。这种技巧可以快速求出任意区间的和，时间复杂度为 O(1)。

算法原理：

• 假设原数组为 a[]，前缀和数组为 S[]，则 S[i] 表示数组 a[] 中前 i 个元素的和。
• 计算前缀和数组时，从左到右依次累加元素即可。

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和

二维前缀和是对二维数组中每个位置的元素，计算其左上部分所有元素的和并存储在一个新的二维数组中。这种技巧可以快速求出任意子矩阵的和，时间复杂度为 O(1)。

算法原理：

• 假设原二维数组为 a[][]，前缀和数组为 S[][]，则 S[i][j] 表示原数组中左上部分所有元素的和。
• 计算前缀和数组时，先按行求出每行的前缀和，然后按列对每行的前缀和进行累加。

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]cpp

一维差分

一维差分是一种数组处理技巧，通过对数组中相邻元素的差值进行存储，可以快速更新区间内的元素。

算法原理：

• 给定原数组 a[] 和差分数组 b[]，则 b[i] = a[i] - a[i-1]。
• 对于原数组中区间 [l, r] 的元素加上常数 c，可以通过修改差分数组 b[l] += c 和 b[r+1] -= c 实现。

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分

二维差分是一种对二维数组进行处理的技巧，通过对二维数组中相邻元素的差值进行存储，可以快速更新子矩阵内的元素。

算法原理：

• 给定原二维数组 a[][] 和差分数组 b[][]，则 b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]。
• 对于原数组中子矩阵 [x1, y1, x2, y2] 内的元素加上常数 c，可以通过修改差分数组的四个角 b[x1][y1] += c、b[x2+1][y1] -= c、b[x1][y2+1] -= c 和 b[x2+1][y2+1] += c 实现。

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

位运算

位运算是一种对整数的二进制表示进行操作的技巧，包括与、或、异或、左移、右移等操作，常用于解决一些位操作相关的问题。

算法原理：

• 位运算可以在底层对整数的二进制表示进行操作，常用于解决一些位级别的问题。
• 例如，通过位运算可以快速判断一个整数的奇偶性、提取某一位的值、计算两个整数的二进制表示中有多少位不同等。

求n的第k位数字: n >> k & 1cpp
返回n的最后一位1：lowbit(n) = n & -n

双指针算法

双指针算法是一种通过使用两个指针在数组或序列中遍历或搜索的技巧，常用于求解滑动窗口、两数之和等问题。

算法原理：

• 双指针算法通常使用两个指针分别指向数组的不同位置，根据具体问题的要求移动指针，实现特定的操作。
• 双指针算法的核心在于寻找合适的条件，确定指针的移动方式。

// 具体问题的逻辑
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;
}

离散化

离散化是一种对原始数据进行映射，将原始数据转换成连续的整数，常用于处理离散值的问题，如区间查询、离散化后的排序等。

算法原理：

• 离散化将原始数据映射到一个连续的整数区间，可以将离散值转换成连续的序列，方便处理。
• 离散化的关键在于去重和排序，然后根据原始数据的大小关系确定映射

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    
    if (st != -2e9) res.push_back({st, ed});
    
    segs = res;
}