文章目录
- 题目链接
- 题目描述
- 解题思路
- 代码实现
- 总结
题目链接
链接: AcWing 802. 区间和
题目描述
解题思路
离散化是一种常用的技巧,它能够将原始的连续数值转换为一组离散的值,从而简化问题的处理。在这段代码中,离散化的过程主要分为三个步骤。
第一步是将需要进行离散化的数值(在这里是add数组和query数组中的x、l、r值)存储到一个数组中(这里是alls数组)。这一步是为了之后的去重和排序做准备。
第二步是对存储了所有待离散化数值的数组进行去重和排序操作。通过这一步,我们得到了一个不重复且有序的离散化数组,能够完整地覆盖所有需要处理的数值。
第三步是使用离散化后的数值进行替换和处理。在这段代码中,对add数组中的操作和query数组中的查询都是通过离散化后的位置来进行处理的,而不再直接使用原始的连续数值。这样做的好处是,在处理过程中不再受到原始数值的大小和分布的影响,简化了问题的处理过程。
离散化核心代码
//离散化 sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()),alls.end());
代码实现
#include
#include #include using namespace std; typedef pair PII; const int N=3e6+10; int n,m; int a[N],s[N]; vector alls;//存储坐标 vector add,query;//读入操作和求值操作 int find(int x) { int l=0,r=alls.size()-1; while(l 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 int x,c; cin>>x>>c; add.push_back({x,c}); alls.push_back(x); } for(int i=0;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()); //处理读入 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< 总结
存储数值:将需要离散化的数值存储到一个数组中,如add和query数组中的x、l、r值都存储在alls数组中。
去重和排序:对存储了所有待离散化数值的数组进行去重和排序操作,得到一个不重复且有序的离散化数组。
替换和处理:使用离散化后的数值进行替换和处理。在这段代码中,操作和查询都是通过离散化后的位置来进行处理的,简化了问题的处理过程。
离散化的目的是将连续的数值转换为离散的数值,从而简化问题的处理。通过离散化,可以减少对原始数值大小和分布的敏感性,使问题的处理更加简单和高效。