做网站有必要用wordpress,天河建设网站企业,常州知名网站建设公司,wordpress去除tag文章目录 离散化的适用条件离散化的意思AcWing 802. 区间和CODECODE2 离散化的适用条件
离散化用于区间求和问题对于数域极大#xff0c;而数的量很少的情况下 离散化的意思
背景#xff1a;对于一个极大数域上的零星几个数进行操作后#xff0c;求某段区间内的和 其实意思… 文章目录 离散化的适用条件离散化的意思AcWing 802. 区间和CODECODE2 离散化的适用条件
离散化用于区间求和问题对于数域极大而数的量很少的情况下 离散化的意思
背景对于一个极大数域上的零星几个数进行操作后求某段区间内的和 其实意思就是大数域映射到一个小数域内。比如我的操作是第 30 30 30 位加 10 10 10第 2000 2000 2000 位加 50 50 50,第 1 0 6 10^6 106 位加 100 100 100映射后我的操作就是a[1] 10a[2] 50a[3] 100也就是说我们将零散的数域变得紧凑。 我们如何做到将序列号变紧密而且不重复呢 首先我们将需要转化的序列号存在一个数组a[]内序列号就是我们在大数域内进行操作时的序列号操作包括对某一号元素进行改值或者是求区间之和的时候区间的左右端点。这些都是大数域上的序列号之后我们将这些序列号进行排序然后去掉重复的号。 这步操作的意思是每个大数域上的序列号在小数域上只能有一个编号与其对应所以需要去除重复的大序列号 我们用数组a[]的下标作为小数域上与大数域相对应的编号所以说我们其实是通过一个数组来将序列号缩小的 最后我们使用前缀和算法快速求得多个询问的区间和即可 AcWing 802. 区间和
题目链接AcWing 802. 区间和 CODE
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;typedef pairint, int pii; // 定义一个pair类型的别名PII用于存储一对整数int n, m; // n和 m 分别表示插入操作和查询操作的数量
const int N 300010; // 定义一个常量N作为数组的大小
int a[N], s[N]; // a数组用于存储每个位置的数值s数组用于存储前缀和vectorint alls; // alls向量用于存储所有出现过的数
vectorpii add, query; // add向量用于存储所有的插入操作query向量用于存储所有的查询操作int l, r; // l和r用于存储查询操作的左右边界
int x, c; // x和c用于存储插入操作的数和次数int find(int x) // find函数用于在alls向量中找到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;
}int main()
{cin n m; // 输入插入操作和查询操作的数量while (n -- ){cin x c;add.push_back({x, c});alls.push_back(x); // 将x加入到alls向量中}while (m -- ){cin l r;query.push_back({l, r});alls.push_back(l); // 将l和r加入到alls向量中alls.push_back(r);}// 去重sort(alls.begin(), alls.end()); // 对alls向量进行排序alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 删除alls向量中的重复元素// 找加入元素的位置并初始化加入数组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){l find(item.first), r find(item.second);printf(%d\n, s[r] - s[l - 1]);}
} 其实由上述过程和代码我们可以发现我们用数组来缩小数域的思路与哈希表不谋而合所以说我们可以用哈希表来存我们的操作数的序列号这样的话能将二分的 O ( l o g n ) O(logn) O(logn) 优化到哈希表的 O ( 1 ) O(1) O(1) 但是我们不能用手写的简易哈希表单指开放寻址和拉链法能优化成map当我没说 因为开放寻址法中我们需要对对所有数进行取模操作而模量N是较小的而数据的编号很大所以就可能出现我们映射的范围出现问题例如一个区间[l, r]我们用的模量N满足 l N r l N r lNr这个时候我们有个尴尬的问题我们的l映射之后比r大那么再对这个区间求和时就回出现错误 这个时候就需要我们伟大的 S T L STL STL 出场了unordered_map很好的解决了我们的问题 不得不说C真的很牛逼啊那老头真吊
CODE2
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;typedef pairint, int pii;int n, m;
const int N 300010;
int a[N], s[N];
vectorint alls;
vectorpii add, query;
int l, r;
int x, c;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;
}int main()
{cin n m;while (n -- ){cin x c;add.push_back({x, c});alls.push_back(x);}while (m -- ){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());unordered_mapint, int indx;for(int i 1; i alls.size(); i) indx[alls[i - 1]] i;// 找加入元素的位置并初始化加入数组for(auto item : add){int x indx[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){l indx[item.first], r indx[item.second];printf(%d\n, s[r] - s[l - 1]);}
}这个代码是我从评论区抄的位置https://www.acwing.com/solution/content/13511/往下翻评论区有个哈希表代码
但是我怎么都看不懂他哈希表的赋值操作
for(int i 1; i alls.size(); i) indx[alls[i - 1]] i;艹为什么 问bing他跟我说因为是我在之前对alls[]数组排序去重了所以区间[l, r]肯定不会映射出错r映射完肯定比l大但是我问他是因为键有序所以导致哈希表映射后相对顺序不变吗它又说不是然后就是一堆我看不懂的谜语一直复读复读复读啊啊啊啊啊啊啊好痛苦啊啊啊啊啊啊
我把对键的赋值改了不赋为i但是又 W A WA WA真的很烦啊想不出来为什么等我以后深入一下 S T L STL STL 再说吧 _蒟蒻是这样的。
