快速排序
快速排序是一种常见且高效的排序算法。其基本思想可以归纳为以下几个步骤：
1.选择一个基准元素（通常是数组的第一个或最后一个元素）作为分割点。
2.将数组中小于基准的元素移动到基准的左边，大于基准的元素移动到右边。这个过程称为分区操作。
3.对分区后的左右两个子数组，重复步骤1和步骤2，直到子数组的大小为1或0，即已经排序完成。
4.最后将所有子数组拼接起来，即得到排好序的数组。
这种分而治之的思想使得快速排序具有较好的平均时间复杂度（O(nlogn)），并且它是一种原地排序算法，不需要额外的辅助空间。
需要注意的是，快速排序的性能高度依赖于选取的基准元素。不同的选择方式可能导致最好情况和最坏情况的时间复杂度差异较大，因此一些优化方法也被提出来，如随机选择基准元素、三数取中法等
模板
#include <iostream>
using namespace std;
const int N=100010;
int q[N];
void quick_sort(int q[],int l,int r)
{
if(l>=r) return ;
int x=q[l + r >> 1], i=l-1, j=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);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0;i < n; i ++ )
{
scanf("%d",&q[i]);
}
quick_sort(q,0,n-1);
for (int i = 0;i < n; i ++ )
{
printf("%d ", q[i]);
}
return 0;
}
归并算法
归并排序是一种经典的分治算法，其原理可以概括为以下几个步骤：
1.将待排序的数组不断划分，直到每个子数组只有一个元素（即递归的将数组二分）。
2.逐个合并相邻的子数组，直到最终合并成一个有序的数组。
具体来说，归并排序的原理是这样的：
1.分割：将待排序数组从中间位置划分为两个子数组，分别递归地对这两个子数组进行分割，直到每个子数组只有一个元素。
2.合并：逐个合并相邻的子数组，将两个有序的子数组合并成一个有序的大数组。合并的过程中，比较两个子数组的元素大小，将较小的元素先放入临时数组。如果一个子数组中的元素已经全部处理完，则将另一个子数组中的剩余元素直接放入临时数组。
3.重复上述合并过程，直到所有子数组合并成一个完整的有序数组。
归并排序的关键点在于合并操作，这个操作是通过比较两个有序的子数组的元素来实现的。合并过程中，需要一个临时数组来存放合并后的有序元素，最后将临时数组中的元素拷贝回原始数组中。
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。它是一种稳定的排序算法，适用于各种数据规模的排序任务。
模板
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];
void 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];
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
scanf("%d", &a[i]);
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i ++ )
printf("%d ", a[i]);
return 0;
}
二分
第一部分 --- 整数二分
基本思想是将有序数组通过每次查找中间元素来判断需要查找的目标元素在左边还是右边。每次查找会将搜索区间减半，这个算法的时间复杂度为 O(log n)。
具体来说，二分法的基本思想是：
确定需要查找的有序数组（通常是升序排列）；
初始化左指针 l 和右指针 r，分别指向数组的左右两端；
在每次循环中计算中间位置 mid，即 mid=(l+r)/2,或者mid=(l+r+1)/2（根据题目来定)
如果目标元素等于中间元素，则查找成功，返回中间元素的下标；
如果目标元素小于中间元素，则在左半部分继续查找，否则在右半部分查找；
重复步骤3到步骤5，直到找到目标元素或搜索区间为空为止。
需要注意的是，二分法通常只适用于有序数组，通过每次将搜索区间减半的方式来提高查找效率。如果数组是无序的，则无法保证每次查找时都可以缩小搜索范围，因此二分法可能不适用。
第二部分 --- 浮点数二分
浮点数二分法是一种在浮点数范围内进行二分查找的方法。与整数二分不同，浮点数二分需要考虑到浮点数的精度问题。
浮点数二分法的基本原理如下：
确定需要查找的浮点数范围，并初始化左边界（low）和右边界（high）。通常情况下，low会初始化为浮点数范围的最小值，high会初始化为浮点数范围的最大值。
在每次循环中，计算中间值（mid）为 (low + high) / 2。
判断中间值mid与目标值的关系：
如果mid与目标值非常接近（可以通过比较它们的绝对差异或相对差异来判断），则可以认为已经找到了目标值，返回mid。
如果mid大于目标值，则目标值可能在左边，在下一轮循环中，将high更新为mid。
如果mid小于目标值，则目标值可能在右边，在下一轮循环中，将low更新为mid。
重复步骤2和步骤3，直到找到目标值或者确定目标值不存在。通常使用一个足够小的阈值（例如10^-6作为判断目标值是否接近的依据。
如果在循环结束后仍未找到目标值，则说明目标值不存在。
需要注意的是，在浮点数的二分查找过程中，由于浮点数的表示存在精度问题，可能会遇到一些额外的问题，例如舍入误差和比较的不确定性等。因此，在具体实现中，可能需要根据具体需求进行一些调整和特殊处理，以保证查找的准确性。
代码模板 — 来自y总的模板
浮点数二分
bool check(double x)
double bsearch_3(double l, double r)
{
const double eps = 1e-6;
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
整数二分
bool check(int x)
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
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;
}
高精度
高精度加法
高精度加法是指对大整数进行加法运算的一种方法，它能够处理超过计算机原生整数范围的整数。
高精度加法的基本原理如下：
首先，将两个大整数从低位（个位）开始逐位相加。同时，使用一个额外的变量（进位标志）来记录进位的情况，初始进位标志为0。
将两个大整数的当前位相加，再加上进位标志。得到的结果就是当前位的和。
如果和大于等于10，则需要进行进位操作。将和除以10得到的商，作为下一位的进位标志；将和除以10得到的余数，作为当前位的结果。
如果和小于10，则不需要进行进位操作。将和直接作为当前位的结果，进位标志为0。
继续从低位向高位进行相加的过程，直到两个大整数的每一位都相加完毕。
如果最高位的相加产生了进位，需要将进位添加到结果的最高位。
最后得到的结果即为两个大整数的和。
需要注意的是，由于大整数可能会非常大，可能超出计算机能表示的范围。因此，在实际编程中，通常会使用数组或者字符串来表示大整数，并且采用逐位相加的方法来进行处理。
高精度加法的时间复杂度为O(n)，其中n是两个大整数的位数之和。它是一种常用的算法，在计算需要处理大整数的场景中非常有用
#include <iostream>
#include <vector>
using namespace std;
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;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
auto C = add(A, B);
for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl;
return 0;
}
高精度减法
高精度减法是指对大整数进行减法运算的一种方法，它能够处理超过计算机原生整数范围的整数。
高精度减法的基本原理如下：
首先，比较被减数和减数的大小，确定哪一个数是较大的数，将较大的数作为被减数，较小的数作为减数。
从低位（个位）开始逐位相减。同时，使用一个额外的变量（借位标志）来记录借位的情况，初始借位标志为0。
将被减数的当前位减去减数的当前位，再减去借位标志。得到的结果就是当前位的差。
如果差小于0，则需要进行借位操作。将差加上10，并将借位标志设置为1。
如果差大于等于0，则不需要进行借位操作。将差直接作为当前位的结果，借位标志为0。
继续从低位向高位进行相减的过程，直到两个大整数的每一位都相减完毕。
如果最高位的相减产生了借位，那么此时差值应为负数，需要将其取相反数，并在结果的最高位加上负号。
最后得到的结果即为两个大整数的差。
需要注意的是，由于大整数可能会非常大，可能超出计算机能表示的范围。因此，在实际编程中，通常会使用数组或者字符串来表示大整数，并且采用逐位相减的方法来进行处理。
高精度减法的时间复杂度为O(n)，其中n是两个大整数的位数之和。它也是一种常用的算法，在计算需要处理大整数的场景中非常有用。
#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B)
{
if (A.size() != B.size()) return A.size() > B.size();
for (int i = A.size() - 1; i >= 0; i -- )
if (A[i] != B[i])
return A[i] > B[i];
return true;
}
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;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
vector<int> C;
if (cmp(A, B)) C = sub(A, B);
else C = sub(B, A), cout << '-';
for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl;
return 0;
}
高精度乘法
高精度乘法是指对大整数进行乘法运算的一种方法，它能够处理超过计算机原生整数范围的整数。
高精度乘法的基本原理如下：
首先，将两个大整数的每一位都与另一个大整数的每一位相乘。记第一个大整数为A，第二个大整数为B。根据乘法的性质，A的第i位与B的第j位相乘的结果应该放在结果的第i+j位上。
创建一个存放结果的数组，长度为A的位数加上B的位数再加1（用来存放可能的进位）。
从A的最低位（个位）开始，逐位与B的每一位进行相乘，得到中间结果。同时，使用一个变量（进位标志）来记录可能的进位，初始进位标志为0。
将中间结果与结果数组对应的位上的数相加，同时考虑进位标志。得到的和即为当前位的结果。
如果和大于等于10，则需要进行进位操作。将和除以10得到的商，作为下一位的进位标志；将和除以10得到的余数，作为当前位的结果。
如果和小于10，则不需要进行进位操作。将和直接作为当前位的结果，进位标志为0。
继续从低位向高位进行相乘和相加的过程，直到A的每一位都与B的每一位相乘完毕。
如果最高位的相乘产生了进位，需要将进位加到结果数组的最高位。
最后得到的结果即为两个大整数的乘积。
需要注意的是，由于大整数可能会非常大，可能超出计算机能表示的范围。因此，在实际编程中，通常会使用数组或者字符串来表示大整数，并且采用逐位相乘和相加的方法来进行处理。
高精度乘法的时间复杂度为O(n^2)，其中n是两个大整数的位数之和。它也是一种常用的算法，在计算需要处理大整数的场景中非常有用。
#include <iostream>
#include <vector>
using namespace std;
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;
}
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> A;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
auto C = mul(A, b);
for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
return 0;
}
高精度除法
高精度除法是指对大整数进行除法运算的一种方法，它能够处理超过计算机原生整数范围的整数。
高精度除法的基本原理如下：
首先，将被除数和除数转换为整数数组。可以使用数组或者字符串来表示大整数。
初始化商和余数为两个空数组。
从被除数的高位（最高位）开始逐位进行除法运算，直到被除数的最低位。
对于每一位的除法运算，需要执行以下步骤：
将之前的余数乘以10，并加上当前位的值，得到当前被除数。
使用当前被除数与除数进行除法运算，得到当前位的商和余数。
将商添加到商数组中，将余数更新为当前余数。
当被除数的最低位计算完毕后，商数组即为最终的商，余数即为最终的余数。
需要注意的是，由于大整数可能会非常大，可能超出计算机能表示的范围。因此，在实际编程中，通常会使用数组或者字符串来表示大整数，并且采用逐位相除的方法来进行处理。
此外，还有一些特殊情况需要特别处理：
如果除数为 0，则除法运算无法进行，需要进行错误处理。
如果被除数为 0，则商为 0，余数也为 0。
如果被除数的高位除以除数小于除数，则商的最高位为 0。
高精度除法的时间复杂度为O(n^2)，其中n是被除数的位数。它也是一种常用的算法，在计算需要处理大整数的场景中非常有用。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
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;
}
int main()
{
string a;
vector<int> A;
int B;
cin >> a >> B;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
int r;
auto C = div(A, B, r);
for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl << r << endl;
return 0;
}
前缀和与差分
前缀和
前缀和，也称为前缀数组、前缀和数组等，它是一种常用的算法
用于高效地处理数组区间求和问题。其原理是利用动态规划的思想
用一个数组 sums 保存原数组 nums 的前缀和，即 sums[i] 表示 nums[0]+nums[1]+…+nums[i] 的值。这样，对于任意一个区间 [left,right] 的和，我们可以用 sums[right]-sums[left-1] 来计算。
具体而言，我们可以通过一次遍历原始数组 nums 来计算出 sums 数组。遍历时，对于每个位置 i，我们将当前位置的元素值加到前一个位置的前缀和上，即 sums[i] = sums[i-1] +nums[i]。这样就可以线性地计算出整个 sums 数组，时间复杂度为 O(n)。
利用前缀和数组，我们可以在 O(1) 的时间内处理区间和问题，大大提高了效率。
相应地，如果存在多次对同一数组进行区间求和操作的情况，就可以重复利用一次计算得到的前缀和数组，避免重复计算。
我举一个具体的例子来说明。假设有一个整数数组 nums = [1, 2, 3, 4, 5]，我们需要实现一个 NumArray 类，并使用该类来计算数组中任意区间的和。
首先，在 NumArray 的构造函数中，我们可以计算该数组的前缀和数组 sums。对于以上的 nums 数组，前缀和数组 sums = [1, 3, 6, 10, 15]，其中 sums[i] 表示 nums[0]+nums[1]+…+nums[i] 的和。
接下来，当我们调用 sumRange 方法时，传入数组的索引范围 [i, j]，我们只需要用前缀和数组 sums 的对应元素相减，即 sums[j] - sums[i-1]，就可以得到该区间的和。
举一个例子，假设我们调用 sumRange(1, 3)，表示计算索引为 1 到 3 的区间和。根据前缀和数组 sums，我们可以得到 sums[3] - sums[0] = 10 - 1 = 9，即该区间 [1, 3] 的和为 9。
同样地，如果我们调用 sumRange(0, 4)，表示计算索引为 0 到 4 的区间和，在前缀和数组 sums 中，我们可以得到 sums[4] - sums[-1] = 15 - 0 = 15，即该区间 [0, 4] 的和为 15。
一道小题
根据上述思路来写代码,代码如下
#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N], ans[N], l, r, n, x, m;
int main()
{
cin >> n >> m;
for (int i = 1;i <= n; i ++ )
{
cin >> x;
ans[i] = x +ans[i-1];
}
while(m--)
{
cin >>l >> r;
cout << ans[r] - ans[l-1] << '\n';
}
return 0;
}
二维前缀和
二维前缀和，也称为二维前缀和数组，是基于前缀和的概念在二维数组上的扩展。它可以用于高效地处理二维数组的区域和问题。其原理是在二维数组上构建一个前缀和数组，用于存储每个位置及其左上角区域的元素和。
具体而言，对于一个二维数组 grid，我们可以构建一个与其相同大小的二维数组 sums，其中 sums[i][j] 表示从 (0,0) 到 (i,j) 这个矩形区域内元素的和。构建二维前缀和数组的过程如下：
遍历原始二维数组 grid，计算每个位置的前缀和，并存储到对应位置的 sums 数组中。
sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + grid[i][j]
其中，sums[i-1][j] 表示上方矩形的和，sums[i][j-1] 表示左侧矩形的和，sums[i-1][j-1] 表示重复计算的左上方矩形的和，grid[i][j] 表示当前位置的元素值。
计算过程需要注意边界情况，当 i-1 或 j-1 索引小于 0 时，上方或左侧矩形的和置为 0。
通过构建好的二维前缀和数组 sums，我们可以在 O(1) 的时间内计算任意一个矩形区域的和。对于给定的矩形区域 [row1, col1, row2, col2]，我们可以用 sums[row2][col2] - sums[row1-1][col2] - sums[row2][col1-1] + sums[row1-1][col1-1] 来计算其和。其中，sums[row2][col2] 表示右下角矩形的和，sums[row1-1][col2] 表示上方矩形的和，sums[row2][col1-1] 表示左侧矩形的和，sums[row1-1][col1-1] 表示重复计算的左上方矩形的和。
通过二维前缀和数组，我们可以高效地处理二维数组的区域和问题，尤其适用于多次对同一二维数组进行区域和计算的场景。
假设有一个二维数组 grid 如下所示：
1 2 3 4
5 6 7 8
9 10 11 12
我们可以利用上述的构建二维前缀和数组的方法，得到以下的二维前缀和数组 sums：
1 3 6 10
6 14 24 36
15 33 54 78
在 sums 数组中，sums[i][j] 表示从 (0,0) 到 (i,j) 这个矩形区域内元素的和。
假设我们现在要计算矩形区域 [1, 1, 2, 2] 的和，利用二维前缀和，我们可以用 sums[2][2] - sums[0][2] - sums[2][0] + sums[0][0] 来得到其和。具体而言，sums[2][2] 表示右下角矩形的和为 54，sums[0][2] 表示上方矩形的和为 6，sums[2][0] 表示左侧矩形的和为 15，sums[0][0] 表示重复计算的左上方矩形的和为 1。将这些值代入公式，得到 54 - 6 - 15 + 1 = 34，即矩形区域 [1, 1, 2, 2] 的和为 34。
通过以上例子，我们可以看到如何利用二维前缀和，以及利用前缀和数组的思想，在 O(1) 的时间内计算任意二维数组的矩形区域和
小题一道
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q,s[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &s[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
while (q -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}
差分
差分是一种常用的技巧，用于在数组中高效地进行区间修改操作。它的原理在于将原始数组转化为差分数组，从而在 O(1) 的时间内完成区间修改。
假设有一个包含 n 个元素的数组 A，我们需要在 A 的某个区间 [start, end] 上进行修改。常规的做法是直接遍历该区间，逐个修改元素。但是，这样的时间复杂度是 O(end - start + 1)，如果区间长度很大，操作会变得非常耗时。
差分数组的思想是，在数组中维护一个新的数组 D，其长度比原始数组 A 长 1。D[i] 表示 A[i] 和 A[i-1] 之间的差值，即 D[i] = A[i] - A[i-1]。通过构建差分数组，我们可以在 O(1) 的时间内完成区间修改。
首先，对于原始数组 A，在进行修改之前，我们需要提前构建好对应的差分数组 D。具体的构建方法如下：
将 D[0] 初始化为 A[0]，即 D[0] = A[0]。
对于 i 从 1 到 n-1，计算 D[i] = A[i] - A[i-1]。
得到差分数组 D 之后，我们只需要在修改区间 [start, end] 进行操作即可。具体的步骤如下：
将 D[start] 增加 value，即 D[start] += value。
将 D[end+1] 减少 value，即 D[end+1] -= value。
通过以上操作，差分数组 D 中表示了对应区间 [start, end] 的增量 value。最后，我们可以通过差分数组 D 计算出新的原始数组 A 如下：
初始化原始数组 A 的第一个元素 A[0] = D[0]。
对于 i 从 1 到 n-1，计算 A[i] = A[i-1] + D[i]。
通过上述步骤，我们可以在 O(1) 的时间内完成对区间 [start, end] 的修改，而不需要遍历整个区间进行操作。这种差分数组的思想在一些需要频繁进行区间修改的场景中非常实用，可以显著提高代码的执行效率。
假设有一个长度为 5 的数组 nums，初始状态如下：
nums = [1, 2, 3, 4, 5]
现在我们需要对数组的区间 [1, 3] 进行增加 2 的操作。传统的做法是遍历该区间的元素，逐个进行修改。但是，通过差分的方法，我们可以省去遍历的过程。
首先，我们构建差分数组 diff，长度比原始数组 nums 长 1：
diff = [0, 0, 0, 0, 0]
然后，根据差分数组的原理，我们对应区间 [1, 3] 进行增加 2 的操作：
diff[1] += 2
diff[4] -= 2
更新后的差分数组 diff 变为：
diff = [0, 2, 0, 0, -2]
最后，我们根据差分数组 diff 来计算新的原始数组 nums，具体的计算过程如下：
nums[0] = diff[0] = 0
nums[1] = nums[0] + diff[1] = 0 + 2 = 2
nums[2] = nums[1] + diff[2] = 2 + 0 = 2
nums[3] = nums[2] + diff[3] = 2 + 0 = 2
nums[4] = nums[3] + diff[4] = 2 + (-2) = 0
最终得到更新后的原始数组 nums：
nums = [0, 2, 2, 2, 0]
通过差分数组的应用，我们成功地在 O(1) 的时间内完成对区间 [1, 3] 的增加 2 操作。这种差分的思想可以帮助我们优化区间修改的效率
小题一道
#include <iostream>
using namespace std;
const int N=1e5+5;
int n, m, a[N], l, r, c, b[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
b[i] = a[i] - a[i - 1];
}
for (int i = 1; i <= m ; i ++ )
{
cin >> l >> r >> c;
b[l] += c;
b[r + 1] -= c;
}
for (int i = 1; i <= n; i ++ )
{
a[i] = a[i - 1] + b[i];
}
for (int i = 1; i <= n; i ++ )
{
cout<< a[i] <<' ';
}
return 0;
}
二维前缀和
二维前缀和是一种常用的技巧，用于在二维数组中高效地进行区域和的查询操作。它的原理在于利用动态规划的思想，通过构建一个前缀和数组来保存从原始数组的起点到每个元素的子矩形和。
假设有一个二维数组 grid，其大小为 m × n。我们的目标是计算任意矩形区域 [top, left, bottom, right] 的子矩形和。通常情况下，直接遍历该区域的元素进行累加计算，时间复杂度是 O((bottom - top + 1) × (right - left + 1))，效率较低。
为了优化查询效率，我们可以通过构建二维前缀和数组 sums 来加速计算。具体的构建方法如下：
初始化 sums 的大小为 (m+1) × (n+1)，并将所有元素初始化为 0。
对于 i 从 1 到 m，j 从 1 到 n，计算 sums[i][j] = grid[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]。
在上述计算的过程中，grid[i-1][j-1] 代表原始数组对应位置的元素，sums[i-1][j] 代表上方矩形的和，sums[i][j-1] 代表左侧矩形的和，而 sums[i-1][j-1] 代表重复计算的左上方矩形的和。通过这种方式，我们将从 (0,0) 到 (i,j) 这个区域内的所有元素的和保存在了 sums[i][j] 中。
构建好二维前缀和数组 sums 之后，我们可以通过下述公式来计算区域 [top, left, bottom, right] 的子矩形和：
area_sum = sums[bottom+1][right+1] - sums[top][right+1] - sums[bottom+1][left] + sums[top][left]
其中，sums[bottom+1][right+1] 表示右下角矩形的和，sums[top][right+1] 表示上方矩形的和，sums[bottom+1][left] 表示左侧矩形的和，sums[top][left] 表示重复计算的左上方矩形的和。通过将这些值代入公式，我们可以在 O(1) 的时间内计算出子矩形的和。
通过使用二维前缀和，我们可以大大提高查询区域和的效率，特别适用于需要重复查询不同区域和的场景，如计算二维矩阵中的最大子矩阵和、矩形区域的平均值等。
好的，我们来看一个具体的二维前缀和的例子。
假设有一个二维数组 grid，大小为 3 × 4：
grid = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
我们现在需要计算出区域 [1, 2, 2, 3] 的子矩形和。
首先，我们按照上述方法构建二维前缀和数组 sums，大小为 4 × 5：
sums = [
[0, 0, 0, 0, 0],
[0, 1, 3, 6, 10],
[0, 6, 14, 24, 36],
[0, 15, 33, 54, 78]
]
接着，我们将区域 [1, 2, 2, 3] 的子矩形和计算出来：
area_sum = sums[2][3] - sums[1][3] - sums[2][1] + sums[1][1]
= 24 - 10 - 14 + 6
= 6
因此，区域 [1, 2, 2, 3] 的子矩形和为 6。
通过二维前缀和的方法，我们只需要预处理一遍，就可以在 O(1) 的时间内计算出任意区域的子矩形和，从而大大提高了查询效率。
小题一道
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int x1, y1, x2, y2, c;
int main()
{
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
insert(i, j, i, j, a[i][j]);
while (q--)
{
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, 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];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
printf("%d ", b[i][j]);
printf("\n");
}
return 0;
}
双指针算法
双指针算法（Two Pointers Algorithm）是一种常用的技巧，用于在数组或链表等数据结构中高效地解决一些问题。该算法通过使用两个指针（通常初始化为数组的首尾或链表的头尾），从两个方向同时遍历数据结构并逐步逼近目标，以达到解决问题的目的。
双指针算法的原理通常可以分为以下几种情况：
静态数组或有序数组：对于静态数组或已排序的数组，可以使用两个指针从头和尾同时向中间遍历，逐步逼近目标或查找满足条件的元素。例如，在一个有序数组中查找两个数的和等于目标值，可以通过双指针从数组的两端开始向内逼近，根据元素和与目标值的比较结果调整两个指针的位置。
动态数组或链表：对于动态数组或链表，可以使用快慢指针或两个指针分别指向不同的节点，实现对数据结构的遍历、查找或判断。例如，判断链表是否有环，可以使用快慢指针，其中一个指针每次移动一步，另一个指针每次移动两步，通过比较两个指针是否相遇来判断是否存在环。
区间合并或重叠判断：对于有序的区间集合，可以使用两个指针分别指向当前合并区间的起始和结束位置，根据区间之间的关系进行合并操作或判断是否重叠。例如，在一组区间中进行合并操作，可以通过比较当前区间与下一个区间的关系，调整指针的位置和合并区间的范围。
双指针算法通常可以在 O(n) 的时间复杂度内完成操作，具有较高的效率。它适用于解决一些数组遍历、查找、合并、重叠判断等问题，常见的应用场景包括双指针法、滑动窗口等。
静态数组或有序数组的遍历
// 有序数组的遍历，从两端向中间逼近
int left = 0, right = nums.size() - 1;
while (left < right) {
// 执行操作
left++;
right--;
}
数组或链表中查找满足条件的元素
// 数组或链表中查找两个数的和等于目标值
int left = 0, right = nums.size() - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
// 执行操作
left++;
right--;
} else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
// 判断链表是否有环
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
// 执行操作
break;
}
}
区间合并或重叠判断
// 区间合并
sort(intervals.begin(), intervals.end());
int i = 0, j = 1;
while (j < intervals.size()) {
if (intervals[i][1] >= intervals[j][0]) {
intervals[i][1] = max(intervals[i][1], intervals[j][1]);
} else {
i++;
intervals[i] = intervals[j];
}
j++;
}
intervals.erase(intervals.begin()+i+1, intervals.end());
// 区间重叠判断
sort(intervals.begin(), intervals.end());
int i = 0, j = 1;
while (j < intervals.size()) {
if (intervals[i][1] >= intervals[j][0]) {
// 执行操作
break;
} else {
i = j;
}
j++;
}
也是十分的简单
没学过进制的可能有点困难
位运算
位运算是一种对二进制位进行操作的运算方式，它直接操作每个二进制位上的0和1，可以高效地进行一些特定的操作。以下是位运算的一些常见原理和应用：
位运算原理：
与运算（&）：对应位置上的两个位都为1时，结果位才为1。
或运算（|）：对应位置上的两个位只要有一个为1时，结果位就为1。
异或运算（^）：对应位置上的两个位相异时，结果位才为1。
取反运算（~）：对每个位取反，即0变为1，1变为0。
左移运算（<<）：将二进制数向左移动指定的位数，右边补0。
右移运算（>>）：将二进制数向右移动指定的位数，左边补符号位或0。
常用的位运算应用：
位与运算（&）可以用来屏蔽某些位，例如将一个数的指定位清零或保留指定位。
位或运算（|）可以用来将某些位设置为指定的值。
异或运算（^）可以用来交换两个数的值，也可以用来判断两个数的奇偶性。
取反运算（~）可以将一个数的每个位取反。
左移运算（<<）和右移运算（>>）可以对一个数进行乘以或除以2的幂次方的运算，因为左移相当于乘以2，右移相当于除以2。
利用异或运算来进行数值交换：a = a ^ b; b = a ^ b; a = a ^ b; （推荐使用，效率高且不涉及临时变量）
判断一个数的奇偶性：(num & 1) == 0 表示偶数，(num & 1) != 0 表示奇数。
以上是位运算的一些常用原理和应用，它们在编程中常常用于优化算法、位掩码操作、数据压缩、位向量等领域。在某些场景下，位运算可以提供效率更高、更简洁的算法实现。
还有大名鼎鼎的lowbit
lowbit 函数通常用于获取一个数的最低位 1 所对应的值，并且可以在位运算中高效地实现。以下是 lowbit 函数的常见实现方式：
int lowbit(int num)
{
return num & (-num);
}
在上述代码中，num & (-num) 的作用是保留 num 的最低位 1 所在的位置，并将其它位置上的值都置为 0。这样得到的结果就是 num 的最低位 1 的取值。
举个例子，假设 num = 12，其二进制表示为 1100。通过 num & (-num) 运算，可以得到结果为 4，因为 4 的二进制表示为 0100，即 num 的最低位 1 的取值。同理，对于 num = 7，求解 num & (-num) 运算，可以得到结果为 1。
需要注意的是，lowbit 函数只对正整数有效，且返回的结果是一个整数（二进制表示只包含一个最低位 1，其它位为 0）。
lowbit 函数在位运算相关的算法中有广泛的应用，例如树状数组,用于进行快速的区间修改和查询操作时会用到 lowbit 函数。
离散化
离散化是一种将连续的数值映射到离散的数值集合中的过程。它常用于处理连续数据，将其转化为离散的表示，以便于进行一些特定的计算和分析。以下是离散化的常见原理和步骤：
确定离散化的区间：
首先，需要确定离散化的区间，即将连续的数值范围划分成若干个离散的区间。根据实际需求和数据分布等因素进行选择。
排序：
将需要离散化的原始数值按照从小到大的顺序进行排序，以便后续的处理。
映射：
遍历排序后的数值，为每个数值分配一个对应的离散化后的数值。可以使用一个映射表或数组来记录原始数值和离散化后的数值之间的对应关系。
使用离散化后的数值：
在后续的计算和处理中，使用离散化后的数值代替原始的连续数值进行操作。
离散化的原理在于将连续的数值转换为离散的数值集合，以方便进行一些统计、查询、排序、分类等操作。离散化的应用场景包括：
处理带有连续数值的离散问题，例如区间查询、频率统计。
将连续的数值转化为离散的特征，用于机器学习和数据挖掘。
使用离散化后的索引进行快速查找和搜索。
优化算法的时间和空间复杂度，例如动态规划等。
需要注意的是，在进行离散化后，原始的连续性信息会丢失，只保留了离散化后的数值对应关系
模板
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
using namespace std;
int n;
int main()
{
ios;
vector<int> a;
cin >> n;
a.resize(n);
for (int i = 0; i < n; i ++ )
{
cin >> a[i];
}
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
n = a.size();
for (int i = 0; i < n; i ++ )
{
cout << a[i] << ' ';
}
return 0;
}
代码解释可以到 Here 来看
区间合并
区间合并是指将重叠的区间进行合并，得到不重叠的更大区间的过程。区间合并常用于处理具有重叠区域的问题，例如合并重叠的时间区间、合并重叠的线段等。以下是区间合并的常见原理和步骤：
排序：
首先，需要将给定的区间按照起始点（或终止点）进行排序，以便后续处理。通常以区间的起始点来进行升序排序。
遍历合并：
遍历排序后的区间，依次考虑每个区间，并进行合并操作。开始时，将第一个区间加入合并结果集中。
如果当前区间与合并结果集中的最后一个区间没有重叠，则直接将当前区间加入合并结果集中。
如果当前区间与合并结果集中的最后一个区间有重叠，则将它们合并为一个更大的区间。合并后的区间的起始点为当前合并结果集中的最后一个区间的起始点，终止点为当前区间和最后一个区间的终止点中的较大值。
返回合并结果：
遍历完成后，得到了合并后的区间集合，即不重叠的更大区间。
区间合并的原理在于通过排序和遍历的方式，逐步合并重叠的区间，最终得到不重叠的更大区间。区间合并常用于解决一些问题，如合并重叠的时间区间、判断是否有重叠区间等。使用合并后的区间集合可以简化计算和处理，提高算法的效率。
需要注意的是，在进行区间合并时，涉及到区间的起始点和终止点的比较和更新，需要仔细处理边界情况，确保算法的正确性和效率。
举个简单的例子
假设有以下区间集合需要进行合并：
区间1：[1, 5]
区间2：[3, 7]
区间3：[4, 9]
区间4：[10, 12]
按照区间的起始点进行排序后：
区间1：[1, 5]
区间2：[3, 7]
区间3：[4, 9]
区间4：[10, 12]
接下来，我们按照区间合并的步骤进行遍历和合并：
首先，将第一个区间 [1, 5] 加入合并结果集中。
考虑第二个区间 [3, 7]。它与合并结果集中的最后一个区间 [1, 5] 有重叠，所以将它们合并为 [1, 7]。合并结果为：
合并结果1：[1, 7]
区间3：[4, 9]
区间4：[10, 12]
接下来，考虑区间 [4, 9]。它与合并结果集中的最后一个区间 [1, 7] 仍有重叠，所以将它们合并为 [1, 9]。合并结果为：
合并结果2：[1, 9]
区间4：[10, 12]
最后，考虑最后一个区间 [10, 12]。它与合并结果集中的最后一个区间 [1, 9] 没有重叠，所以直接将它加入合并结果集中。合并结果为：
合并结果3：[1, 9]
区间4：[10, 12]
最终得到合并后的区间集合，不重叠的更大区间为：
合并结果集：[1, 9], [10, 12]
这样就完成了区间的合并。注意，合并结果集中的区间是不重叠的、更大的区间，可以用于进行进一步的计算和处理。
小题一道
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -INT_MAX, ed = -INT_MAX;
for (auto seg : segs)
{
if (ed < seg.first)
{
if (st != -INT_MAX)
res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else
ed = max(ed, seg.second);
}
if (st != -INT_MAX)
res.push_back({st, ed});
segs = res;
}
int main()
{
int n;
cin >> n;
vector<PII> segs;
for (int i = 0; i < n; i ++ )
{
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << '\n';
return 0;
}
当然也可以用贪心来做
