离散化技术实战用C高效处理十亿级区间和问题在算法竞赛和面试中我们经常会遇到需要处理极大值域区间操作的问题。想象一下当题目给出10^9量级的坐标范围却只有10^5次操作时传统的数组存储方式会立即崩溃——内存无法容纳如此庞大的空间。这正是离散化技术大显身手的时刻。1. 问题场景与离散化核心思想AcWing 802区间和问题描述了一个典型的大值域稀疏操作场景在一个无限长的数轴上我们需要对某些离散坐标进行加减操作然后查询任意区间内的数字和。直接开数组存储每个坐标的值显然不现实因为10^9的量级会消耗约4GB内存。离散化的本质是将稀疏分布的数据点重新映射到紧凑的连续空间中。举个例子原始坐标序列[1, 3, 100, 2000, 50000] 离散化映射后[0, 1, 2, 3, 4]离散化三大核心步骤收集所有需要处理的坐标点插入点和查询边界排序并去重建立有序坐标集合通过二分查找实现原始坐标到离散索引的快速映射vectorint alls; // 存储所有待离散化的坐标 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());2. AcWing 802问题的离散化解决方案让我们拆解这个经典问题的解决流程。输入包含n次位置加法操作和m次区间查询数据范围都在10^5量级但坐标值可能达到±10^9。2.1 数据结构设计我们需要准备以下核心数据结构const int N 3e5 10; // n2m的最大可能 int a[N], s[N]; // 离散化数组及其前缀和 vectorint alls; // 离散化坐标集合 vectorPII add, query; // 操作和查询暂存为什么是30万因为最坏情况下n个插入点和2m个查询边界都会进入alls数组。2.2 关键操作分步实现坐标收集阶段// 添加操作收集 for(int i0; in; i){ int x, c; cin x c; add.push_back({x, c}); alls.push_back(x); } // 查询操作收集 for(int i0; im; i){ int l, r; cin l r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); }离散化处理阶段// 排序去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 二分查找映射函数 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-based索引 }注意这里返回r1是为了让离散化后的索引从1开始方便后续前缀和计算。如果返回r则需要调整前缀和的处理方式。3. 完整解决方案与性能分析将所有组件组合起来我们得到完整的解决方案#include iostream #include vector #include algorithm using namespace std; typedef pairint, int PII; const int N 3e5 10; int a[N], s[N]; vectorint alls; vectorPII add, query; int find(int x) { /* 二分查找实现 */ } int main() { int n, m; cin n m; /* 收集所有坐标 */ /* 离散化处理 */ // 执行添加操作 for(auto item : add){ int x find(item.first); a[x] item.second; } // 构建前缀和数组 for(int i1; ialls.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; }时间复杂度分析排序去重O((n2m)log(n2m))每次查找O(log(n2m))总体复杂度O((n2m)log(n2m))完全适用于10^5量级的数据4. 实战模拟与边界处理让我们通过具体样例验证算法的正确性输入样例3 3 1 2 3 6 7 5 1 3 4 6 7 8处理流程收集所有坐标add中的1,3,7和query中的1,3,4,6,7,8排序去重后的alls数组[1,3,4,6,7,8]离散化映射1→1, 3→2, 4→3, 6→4, 7→5, 8→6执行加法操作a[1]2, a[2]6, a[5]5构建前缀和s[1]2, s[2]8, s[3]8, s[4]8, s[5]13, s[6]13处理查询[1,3]→s[2]-s[0]8[4,6]→s[4]-s[2]0[7,8]→s[6]-s[4]5边界情况处理坐标重复通过unique确保唯一性查询边界超出操作范围离散化会自动包含这些边界负数坐标排序比较依然有效5. 离散化技术的扩展应用离散化不仅适用于区间和问题在以下场景同样表现出色大规模稀疏矩阵处理当矩阵中非零元素极少时可以用离散化记录有效位置坐标压缩在计算几何中将浮点数坐标映射到整数空间时间点处理对离散时间事件进行压缩处理// 二维离散化示例 vectorint xs, ys; // 分别存储x和y坐标 // ...收集所有坐标... sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); // y坐标同理处理在实际编码竞赛中建议将离散化部分封装成可重用组件。例如struct Discretizer { vectorint vals; void add(int x) { vals.push_back(x); } void process() { sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); } int get(int x) { return lower_bound(vals.begin(), vals.end(), x) - vals.begin() 1; } };这种封装方式可以简化主逻辑代码减少重复编码错误。
别再硬算10^9的区间和了！用C++离散化搞定AcWing 802（附完整代码与模拟）
发布时间：2026/6/12 22:29:09
离散化技术实战用C高效处理十亿级区间和问题在算法竞赛和面试中我们经常会遇到需要处理极大值域区间操作的问题。想象一下当题目给出10^9量级的坐标范围却只有10^5次操作时传统的数组存储方式会立即崩溃——内存无法容纳如此庞大的空间。这正是离散化技术大显身手的时刻。1. 问题场景与离散化核心思想AcWing 802区间和问题描述了一个典型的大值域稀疏操作场景在一个无限长的数轴上我们需要对某些离散坐标进行加减操作然后查询任意区间内的数字和。直接开数组存储每个坐标的值显然不现实因为10^9的量级会消耗约4GB内存。离散化的本质是将稀疏分布的数据点重新映射到紧凑的连续空间中。举个例子原始坐标序列[1, 3, 100, 2000, 50000] 离散化映射后[0, 1, 2, 3, 4]离散化三大核心步骤收集所有需要处理的坐标点插入点和查询边界排序并去重建立有序坐标集合通过二分查找实现原始坐标到离散索引的快速映射vectorint alls; // 存储所有待离散化的坐标 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());2. AcWing 802问题的离散化解决方案让我们拆解这个经典问题的解决流程。输入包含n次位置加法操作和m次区间查询数据范围都在10^5量级但坐标值可能达到±10^9。2.1 数据结构设计我们需要准备以下核心数据结构const int N 3e5 10; // n2m的最大可能 int a[N], s[N]; // 离散化数组及其前缀和 vectorint alls; // 离散化坐标集合 vectorPII add, query; // 操作和查询暂存为什么是30万因为最坏情况下n个插入点和2m个查询边界都会进入alls数组。2.2 关键操作分步实现坐标收集阶段// 添加操作收集 for(int i0; in; i){ int x, c; cin x c; add.push_back({x, c}); alls.push_back(x); } // 查询操作收集 for(int i0; im; i){ int l, r; cin l r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); }离散化处理阶段// 排序去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 二分查找映射函数 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-based索引 }注意这里返回r1是为了让离散化后的索引从1开始方便后续前缀和计算。如果返回r则需要调整前缀和的处理方式。3. 完整解决方案与性能分析将所有组件组合起来我们得到完整的解决方案#include iostream #include vector #include algorithm using namespace std; typedef pairint, int PII; const int N 3e5 10; int a[N], s[N]; vectorint alls; vectorPII add, query; int find(int x) { /* 二分查找实现 */ } int main() { int n, m; cin n m; /* 收集所有坐标 */ /* 离散化处理 */ // 执行添加操作 for(auto item : add){ int x find(item.first); a[x] item.second; } // 构建前缀和数组 for(int i1; ialls.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; }时间复杂度分析排序去重O((n2m)log(n2m))每次查找O(log(n2m))总体复杂度O((n2m)log(n2m))完全适用于10^5量级的数据4. 实战模拟与边界处理让我们通过具体样例验证算法的正确性输入样例3 3 1 2 3 6 7 5 1 3 4 6 7 8处理流程收集所有坐标add中的1,3,7和query中的1,3,4,6,7,8排序去重后的alls数组[1,3,4,6,7,8]离散化映射1→1, 3→2, 4→3, 6→4, 7→5, 8→6执行加法操作a[1]2, a[2]6, a[5]5构建前缀和s[1]2, s[2]8, s[3]8, s[4]8, s[5]13, s[6]13处理查询[1,3]→s[2]-s[0]8[4,6]→s[4]-s[2]0[7,8]→s[6]-s[4]5边界情况处理坐标重复通过unique确保唯一性查询边界超出操作范围离散化会自动包含这些边界负数坐标排序比较依然有效5. 离散化技术的扩展应用离散化不仅适用于区间和问题在以下场景同样表现出色大规模稀疏矩阵处理当矩阵中非零元素极少时可以用离散化记录有效位置坐标压缩在计算几何中将浮点数坐标映射到整数空间时间点处理对离散时间事件进行压缩处理// 二维离散化示例 vectorint xs, ys; // 分别存储x和y坐标 // ...收集所有坐标... sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); // y坐标同理处理在实际编码竞赛中建议将离散化部分封装成可重用组件。例如struct Discretizer { vectorint vals; void add(int x) { vals.push_back(x); } void process() { sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); } int get(int x) { return lower_bound(vals.begin(), vals.end(), x) - vals.begin() 1; } };这种封装方式可以简化主逻辑代码减少重复编码错误。
的完整路径（附源码）)
