Loading... # 基础算法1 > **特别声明:** 本博客是我在学习[acwing网站](https://www.acwing.com/)中的算法课程中所记录的笔记, 部分资源来源于网络, 如果有侵权,请及时联系作者删除相关的部分. > > 如果有错误可以私信作者(qq:**1351798781**)进行更改, 非常感谢. > > 欢迎够买[正版ACwing课程](https://www.acwing.com/activity)(不是广告, ACwing没有打钱). # 1 快速排序 1. 确认分界点 : q[l], q[(l + r) / 2], q[r], 随机; 2. 调整范围:左边 <= x, 右边 >= x; 3. 递归处理左右两段. **暴力方法:** 4. a[], b[]; 5. q[l~r]:x->a[] (q[i] <= x), x->b[] (q[i] >= x); 6. a[]->q[], b[]->q[]; ### [785. 快速排序](https://www.acwing.com/problem/content/787/) 输入格式: 整数n和n个整数; 输出格式: 排好序的数列. ```c++ const int N = 1e6 + 10; int n, q[N]; void quick_sort(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(l, j); quick_sort(j + 1, r); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &q[i]); quick_sort(0, n - 1); for (int i = 0; i < n; i++) printf("%d ", q[i]); return 0; } ``` ### [786. 第k个数](https://www.acwing.com/problem/content/788/) 给定一个长度为 n 的整数数列, 以及一个整数 k, 请用快速选择算法求出数列从小到大排序后的第 k 个数. > 快速选择算法: > > 1. 选取一个基准(参考快排), 将数组分成左右两个部分, 右边部分大于等于左边部分. > 2. 根据数组分界位置与k的大小关系, 判断要找的数字是在左半部分还是右半部分. > 3. 对存在要找数字的那半部分数组递归处理, 直到待处理的数组中只剩下一个数, 这个数字就是要找的那个. ```c++ const int N = 1e5 + 10; int n, k; int q[N]; int quick_sort(int l, int r, int k) { //数组中就剩一个数了, 就是要找的那个数字 if (l == r) return q[l]; int i = l - 1, j = r + 1, x = q[(l + r) >> 1]; while (i < j) { while (q[++i] < x); while (q[--j] > x); if (i < j) swap(q[i], q[j]); } //(左)l--j,(右)j+1--n,s1是左边数的个数 int s1 = j - l + 1; //如果k在分界线左边, 处理左半部分数组 if (k <= s1) return quick_sort(l, j, k); //否则k在分界线右边, 处理左半部分数组 return quick_sort(j + 1, r, k - s1); } int main() { scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &q[i]); printf("%d\n", quick_sort(0, n-1, k)); return 0; } ``` # 2 归并排序 1. 确定分界点: mid = (l + r) / 2; 2. 递归排序: left和right; 3. 归并->合二为一. ### [787. 归并排序](https://www.acwing.com/problem/content/789/) 输入格式 : 整数n和n个整数; 输出格式: 排好序的数列. ```c++ const int N = 1e5 + 10; int n, q[N], tmp[N]; void merge_sort(int l, int r) { if (l >= r) return; int mid = (l + r) >> 1; merge_sort(l, mid); merge_sort(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 (int i = l, j = 0; i <= r; i++, j++)q[i] = tmp[j]; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &q[i]); merge_sort(0, n - 1); for (int i = 0; i < n; i++) printf("%d ", q[i]); return 0; } ``` ### [788. 逆序对的数量](https://www.acwing.com/problem/content/790/) 给定一个长度为 n 的整数数列, 请你计算数列中的逆序对的数量. 逆序对的定义如下: 对于数列的第 i 个和第 j 个元素, 如果满足 i<j 且 a[i]>a[j], 则其为一个逆序对; 否则不是. ![Hongda_2022-11-28_09-10-48](https://www.rearwaves.com/usr/assets/algorithm/basic/Hongda_2022-11-28_09-10-48.png) ```c++ #include <iostream> using namespace std; typedef long long ll; const int N = 1e5 + 10; int n; int q[N], tmp[N]; ll merge_sort(int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; ll res = merge_sort(l, mid) + merge_sort(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++]; res += mid - i + 1; } } //扫尾 while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; //物归原主 for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; return res; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> q[i]; cout << merge_sort(0, n - 1) << endl; return 0; } ``` # 3 二分 ## 3.1 整数二分 模板: ```c++ 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; //注意l=mid时需要l+r+1 if (check(mid)) l = mid; else r = mid - 1; } return l; } ``` ### [789. 数的范围(整数二分)](https://www.acwing.com/problem/content/791/) 给定一个按照升序排列的长度为n的整数数组, 以及q个查询, 对于每个查询, 返回一个元素k的起始位置和终止位置(位置从0开始计数), 如果数组中不存在该元素, 则返回"-1 -1". ```c++ const int N = 1e5 + 10; int n, m; int q[N]; int lower(int l, int r, int x) { while (l < r) { int mid = (l + r) >> 1; if (q[mid] >= x) r = mid; else l = mid + 1; } return r; } int upper(int l, int r, int x) { while (l < r) { int mid = (l + r + 1) >> 1; if (q[mid] <= x) l = mid; else r = mid - 1; } return l; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &q[i]); while (m--) { int k; scanf("%d", &k); int l = lower(1, n, k); if (q[l] != k) printf("-1 -1\n"); else { int r = upper(1, n, k); printf("%d %d\n", l - 1, r - 1); } } return 0; } ``` ## 3.2 浮点数二分 模板: ```c++ bool check(double x) {/* ... */} // 检查x是否满足某种性质 double bsearch_3(double l, double r) { const double eps = 1e-8; // eps 表示精度, 取决于题目对精度的要求, 多计算两位 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; } ``` ### [790. 数的三次方根(浮点数二分)](https://www.acwing.com/problem/content/792/) 给定一个浮点数 n , 求它的三次方根, 结果保留 6 位小数. ```c++ const double eps = 1e-8; double x; int main() { scanf("%lf", &x); double l = -1000, r = 1000; while (r - l > eps) { double mid = (l + r) / 2; if (mid * mid * mid <= x) l = mid; else r = mid; } printf("%.6lf", l); return 0; } ``` # 4 高精度 A+B, A-B: A($10^6$), B($10^6$); $A \times a, \ A \div a$: $len(A) \le 10^6$ $a \le 10^9$; 大整数的存储: 123456789, 存在数组里面.数组q[]={987654321}, 因为需要进位; ### [791. 高精度加法](https://www.acwing.com/problem/content/793/) 模拟人工的加法计算: $A_3A_2A_1A_0+B_2B_1B_0$, 每一位相加要加上一位的进位; ```c++ //vc=va+vb vector<int> add(vector<int>& va, vector<int>& vb) { vector<int> vc; int t = 0; //进位 for (int i = 0; i < va.size() || i < vb.size(); i++) { if (i < va.size()) t += va[i]; if (i < vb.size()) t += vb[i]; vc.push_back(t % 10); t /= 10; } if (t) vc.push_back(1); return vc; } int main() { string a, b; vector<int> va, vb; cin >> a >> b; //a="123456" for (int i = a.size() - 1; i >= 0; i--) va.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i--) vb.push_back(b[i] - '0'); auto vc = add(va, vb); for (int i = vc.size() - 1; i >= 0; i--) printf("%d", vc[i]); return 0; } ``` **压九位算法:** ```c++ const int base = 1000000000; 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 % base); t /= base; } 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, s = 0, j = 0, t = 1; i >= 0; i--) { s += (a[i] - '0') * t; j++, t *= 10; if (j == 9 || i == 0) { A.push_back(s); s = j = 0; t = 1; } } for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i--) { s += (b[i] - '0') * t; j++, t *= 10; if (j == 9 || i == 0) { B.push_back(s); s = j = 0; t = 1; } } auto C = add(A, B); cout << C.back(); for (int i = C.size() - 2; i >= 0; i--) printf("%09d", C[i]); cout << endl; return 0; } ``` ### [792. 高精度减法](https://www.acwing.com/problem/content/794/) 模拟人工的减法计算: $A_3A_2A_1A_0-B_2B_1B_0$, 如果A>=B, 计算A-B;如果B>=A, 算-(B-A).注意借位 $A_i-B_i-t\begin{cases} \ge 0 ,& A_i-B_i-t\\ <0 ,& A_i-B_i+10-t\\ \end{cases}$; ```c++ //判断是否有va>=vb bool cmp(vector<int>& va, vector<int>& vb) { if (va.size() != vb.size()) return va.size() > vb.size(); for (int i = va.size() - 1; i >= 0; i--) { if (va[i] != vb[i]) return va[i] > vb[i]; } return true; } //vc=va-vb vector<int> sub(vector<int>& va, vector<int>& vb) { vector<int> vc; int t = 0; for (int i = 0; i < va.size(); i++) { t = va[i] - t; if (i < vb.size()) t -= vb[i]; vc.push_back((t + 10) % 10); t = t < 0 ? 1 : 0; } //把前导0去掉 while (vc.size() > 1 && vc.back() == 0) vc.pop_back(); return vc; } int main() { string a, b; vector<int> va, vb; cin >> a >> b; //a="123456" for (int i = a.size() - 1; i >= 0; i--) va.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i--) vb.push_back(b[i] - '0'); if (cmp(va, vb)) { auto vc = sub(va, vb); for (int i = vc.size() - 1; i >= 0; i--) printf("%d", vc[i]); } else { auto vc = sub(vb, va); printf("-"); for (int i = vc.size() - 1; i >= 0; i--) printf("%d", vc[i]); } return 0; } ``` ### [793. 高精度乘法](https://www.acwing.com/problem/content/795/) 模拟人工的乘法计算: $A_2A_1A_0 \times b=C_3C_2C_1C_0, \ C_0=(A_0\times b)\%10$ ```c++ //vc=va*b vector<int> mul(vector<int>& va, int b) { vector<int> vc; int t = 0; for (int i = 0; i < va.size() || t; i++) { if (i < va.size()) t += va[i] * b; vc.push_back(t % 10); t /= 10; } //把前导0去掉 while (vc.size() > 1 && vc.back() == 0) vc.pop_back(); return vc; } int main() { string a; int b; vector<int> va; cin >> a >> b; //a="123456" for (int i = a.size() - 1; i >= 0; i--) va.push_back(a[i] - '0'); auto vc = mul(va, b); for (int i = vc.size() - 1; i >= 0; i--) printf("%d", vc[i]); return 0; } ``` ### [794. 高精度除法](https://www.acwing.com/problem/content/796/) 模拟人工的除法计算: $A_3A_2A_1A_0 \div b=C_3C_2C_1C_0$, 计算机很傻,需要一位一位地看; ```c++ //vc=va/b, 商是vc, 余数是r vector<int> div(vector<int>& va, int b, int &r) { vector<int> vc; r = 0; for (int i = va.size() - 1; i >= 0; i--) { r = r * 10 + va[i]; vc.push_back(r / b); r %= b; } reverse(vc.begin(), vc.end()); while (vc.size() > 1 && vc.back() == 0) vc.pop_back(); return vc; } int main() { string a; int b; vector<int> va; cin >> a >> b; //a="123456" for (int i = a.size() - 1; i >= 0; i--) va.push_back(a[i] - '0'); int r; auto vc = div(va, b, r); for (int i = vc.size() - 1; i >= 0; i--) printf("%d", vc[i]); cout << endl << r << endl; return 0; } ``` # 5 前缀和与差分 ## 5.1 前缀和 **一维前缀和: ** 原数组: a[1], a[2], a[3], a[4], a[5], …, a[n] 前缀和 Si为数组的前 i 项和 前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i] 前缀和的作用: 快速求出元素组中某段区间的和 ### [795. 前缀和](https://www.acwing.com/problem/content/797/) 输入一个长度为 n 的整数序列. 接下来再输入 m 个询问, 每个询问输入一对 l,r. 对于每个询问, 输出原序列中从第 l 个数到第 r 个数的和. ```c++ const int N = 1e5 + 10; int n, m; int a[N], s[N]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; while (m--) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", s[r] - s[l - 1]); } return 0; } ``` **二维前缀和: ** 计算方法: `s[i][j] = s[i-1][j] + s[i][j-1] + a[i][j] - s[i-1][j-1]` ![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/basic/二维前缀和1.png) 以(x1, y1)为左上角, (x2, y2)为右下角的子矩阵的和为: `s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]` ![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/basic/二维前缀和2.png) ### [796. 子矩阵的和](https://www.acwing.com/problem/content/798/) 输入一个 n 行 m 列的整数矩阵, 再输入 q 个询问, 每个询问包含四个整数 x1,y1,x2,y2, 表示一个子矩阵的左上角坐标和右下角坐标. 对于每个询问输出子矩阵中所有数的和. ```c++ const int N = 1010; int n, m, q; int a[N][N], 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", &a[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] + a[i][j]; 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; } ``` ## 5.2 差分 **一维差分** 构造一个数组b : b[1] ,b[2] , b[3], ......, b[i]; 使得 a[i] = b[1] + b[2]+ b[3] + ...... + b[i]. a[0]= 0; b[1] = a[1] - a[0]; b[2] = a[2] - a[1]; b[3] =a [3] - a[2]; ........ b[n] = a[n] - a[n-1]; ### [797. 差分](https://www.acwing.com/problem/content/799/) 输入一个长度为 n 的整数序列. 接下来输入 m 个操作, 每个操作包含三个整数 l,r,c, 表示将序列中 [l,r] 之间的每个数加上 c. 请你输出进行完所有操作后的序列. **解题思路:** `b[l] + c`, 效果使得a数组中 a[l] 及以后的数都加上了c(红色部分), 但我们只要求l到r区间加上c, 因此还需要执行 `b[r+1] - c`,让a数组中 a[r+1] 及往后的区间再减去c(绿色部分), 这样对于 a[r] 以后区间的数相当于没有发生改变. ![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/basic/一维差分计算.png) ```c++ const int N = 1e5 + 10; int n, m; int a[N], b[N]; void insert(int l, int r, int c) { b[l] += c; b[r + 1] -= c; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //将序列中[i,i]中的元素都加上a[i], 即初始化差分数组 for (int i = 1; i <= n; i++) insert(i, i, a[i]); while (m--) { int l, r, c; scanf("%d%d%d", &l, &r, &c); insert(l, r, c); } for (int i = 1; i <= n; i++) b[i] += b[i - 1]; for (int i = 1; i <= n; i++) printf("%d ", b[i]); return 0; } ``` **二维差分** ![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/basic/二维差分描述.png) ### [798. 差分矩阵](https://www.acwing.com/problem/content/800/) 输入一个 n 行 m 列的整数矩阵, 再输入 q 个操作, 每个操作包含五个整数 x1,y1,x2,y2,c, 其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标. 每个操作都要将选中的子矩阵中的每个元素的值加上 c. 请你将进行完所有操作后的矩阵输出. ```c++ const int N = 1010; int n, m, q; 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 main() { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &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--) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; insert(x1, y1, x2, y2, c); } //计算b[i][j]的二维前缀和得到结果 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]); puts(""); } return 0; } ``` # 6 双指针算法 常见问题分类: (1) 对于一个序列, 用两个指针维护一段区间; (2) 对于两个序列, 维护某种次序, 比如归并排序中合并两个有序序列的操作. **模板:** ```c++ for(i=0,j=0;i<n;i++){ while(j<i&&check(i,j)) j++; //每道题目的具体逻辑 } ``` ### [799. 最长连续不重复子序列]() 给定一个长度为 n 的整数序列, 请找出最长的不包含重复的数的连续区间, 输出它的长度. **解题思路:** 双指针: 遍历数组a中的每一个元素a[i], 对于每一个i, 找到j使得双指针[j, i]维护的是以a[i]结尾的最长连续不重复子序列, 长度为i - j + 1, 将这一长度与r的较大者更新给r. 对于每一个i, 如何确定j的位置: 由于[j, i - 1]是前一步得到的最长连续不重复子序列, 所以如果[j, i]中有重复元素, 一定是a[i], 因此右移j直到a[i]不重复为止(由于[j, i - 1]已经是前一步的最优解, 此时j只可能右移以剔除重复元素a[i], 不可能左移增加元素, 因此, j具有“单调性”、本题可用双指针降低复杂度). 用数组s记录子序列a[j ~ i]中各元素出现次数, 遍历过程中对于每一个i有四步操作: cin元素a[i] -> 将a[i]出现次数s[a[i]]加1 -> 若a[i]重复则右移j(s[a[j]]要减1) -> 确定j及更新当前长度i - j + 1给r. ```c++ const int N = 1e5 + 10; int n; int a[N], s[N]; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; int res = 0; for (int i = 0, j = 0; i < n; i++) { s[a[i]]++; while (s[a[i]] > 1) { s[a[j]]--; j++; } res = max(res, i - j + 1); } cout << res << endl; return 0; } ``` ### [800. 数组元素的目标和](https://www.acwing.com/problem/content/802/) 给定两个升序排序的有序数组 A 和 B, 以及一个目标值 x. 数组下标从 0 开始. 请你求出满足 A[i]+B[j]=x 的数对 (i,j). 数据保证有唯一解. ```c++ const int N = 1e5 + 10; int n, m, x; int a[N], b[N]; int main() { scanf("%d%d%d", &n, &m, &x); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int j = 0; j < m; j++) scanf("%d", &b[j]); for (int i = 0, j = m - 1; i < n; i++) { while (j >= 0 && a[i] + b[j] > x) j--; if (a[i] + b[j] == x) { printf("%d %d\n", i, j); break; } } return 0; } ``` ### [2816. 判断子序列](https://www.acwing.com/problem/content/2818/) 给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm. 请你判断 a 序列是否为 b 序列的子序列. 子序列指序列的一部分项按**原有次序排列**而得的序列, 例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列. **解题思路:** 用 i 指针扫描 A 序列, j 指针扫描 B 序列, 两个指针初始为序列的最左侧, 然后我们每次判断 Ai 是否等于 Bj, 如果等于, 就让 i 往后一位, 每次让 j 指针往后一位. 如果最后 A 中的每一个数都匹配上了, 就说明匹配成功, 否则匹配失败. ```c++ const int N = 1e5 + 10; int n, m; int a[N], b[N]; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < m; i++) scanf("%d", &b[i]); int i = 0, j = 0; while (i < n && j < m) { if (a[i] == b[j]) i++; j++; } if (i == n) puts("Yes"); else puts("No"); return 0; } ``` # 7 位运算 1、n的二进制表示中第k位是几 方法: 先把第k位移到最后一位 `n >> = k`, 看个位是几 `n & 1`. 最终结果为 `n >> k & 1` 2、lowbit(x): 返回x的最后一位1 x=1010 lowbit(x)=10 x=101000 lowbit(x)=1000 操作: `x & (− x) = x & (~x + 1)` ### [801. 二进制中1的个数](https://www.acwing.com/problem/content/803/) 给定一个长度为 n 的数列, 请你求出数列中每个数的二进制表示中 1 的个数. ```c++ int lowbit(int x) { return x & -x; } int main() { int n; cin >> n; while (n--) { int x = 0; cin >> x; int res = 0; while (x) x -= lowbit(x), res++; //每次减去x的最后一位1 cout << res << ' '; } return 0; } ``` # 8 离散化 ### [802. 区间和](https://www.acwing.com/problem/content/804/) 假定有一个无限长的数轴, 数轴上每个坐标上的数都是 0. 现在, 我们首先进行 n 次操作, 每次操作将某一位置 x 上的数加 c. 接下来, 进行 m 次询问, 每个询问包含两个整数 l 和 r, 你需要求出在区间 [l,r] 之间的所有数的和. **解题思路:** ![区间和题解.png](https://www.rearwaves.com/usr/assets/algorithm/basic/13021_4a9746ee04-区间和题解.png) ```c++ //坐标x的数量上限为1e5, 两个坐标l,r的数量上限也为1e5,所以加起来为3*le5; const int N = 3e5 + 10; //n次插入和m次查询相关数据量的上界 int n, m; int a[N], s[N]; //离散化后坐标插入的值和前缀和 vector<int> alls; //存储(所有与插入和查询有关的)坐标 vector<PII> add, query; //存储题目中原始的插入和询问操作的数据 //使用二分查找x所在的位置, 此时是alls(x,l,r)排好序的,返回的坐标也会是按照x的大小所给出的; int find(int 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; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { int x, c; cin >> x >> c; add.push_back({ x, c }); alls.push_back(x); //坐标x待离散化 } for (int i = 0; i < m; i++) { int l, r; cin >> l >> r; query.push_back({ l, r }); alls.push_back(l); //左边界l待离散化 alls.push_back(r); //右边界r待离散化 } //去重 sort(alls.begin(), alls.end()); //将所有值排序 alls.erase(unique(alls.begin(), alls.end()), alls.end()); //处理插入 for (auto item : add) { int x = find(item.first); a[x] += item.second; } //预处理前缀和 for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i]; //处理询问 for (auto item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; } ``` 手动实现unique函数: ```c++ vector<int>::iterator unique(vector<int>& a) { int j = 0; for (int i = 0; i < a.size(); i++) if (!i || a[i] != a[i - 1]) a[j++] = a[i]; //a[0] ~ a[j-1]所有a中不重复的数 return a.begin() + j; } ``` find函数也可以用lower_bound()来实现. ```c++ int find(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1; } ``` # 9 区间合并 ### [803. 区间合并](https://www.acwing.com/problem/content/805/) 给定 n 个区间 [li,ri], 要求合并所有有交集的区间. 注意如果在端点处相交, 也算有交集. 输出合并完成后的区间个数. 例如: [1,3] 和 [2,6] 可以合并为一个区间 [1,6]. > 可以先按左端点排序, 再维护一个区间, 与后面一个个区间进行三种情况的比较, 存储到数组里去. ```c++ void merge(vector<PII>& segs) { vector<PII> res; sort(segs.begin(), segs.end()); //按左端点排序 int st = -2e9, ed = -2e9; //维护当前的区间 for (auto seg : segs) { //情况1: 两个区间无法合并 //当前区间 |------------| //下一个区间 |----| if (ed < seg.first) { //把当前区间放入结果中,维护下一个区间 if (st != -2e9) res.push_back({ st, ed }); st = seg.first, ed = seg.second; } //情况2: 两个区间可以合并, 且区间1和区间2有交集 //当前区间 |------------| //下一个区间 |----------| else ed = max(ed, seg.second); //情况3: 区间1包含区间2, 此时不需要任何操作, 可以省略 } if (st != -2e9) res.push_back({ st, ed }); segs = res; //把得到的结果赋值给segs } int main() { int n; scanf("%d", &n); vector<PII> segs; for (int i = 0; i < n; i++) { int l, r; scanf("%d%d", &l, &r); segs.push_back({ l, r }); } merge(segs); cout << segs.size() << endl; return 0; } ``` 最后修改:2023 年 04 月 16 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏