对于本题详细的题解可以点击下面的B站链接,对这道题有详细的视频讲解
B站链接:
解答本题需要的知识基础:二分,前缀和,离散化(new)
首先:什么是离散化?
离散化就是:把无限空间中有限的个体映射到有限的空间中去
无限:就是我们这里说的x,因为题中说是一个无限长的数轴(其实 x是有数据范围的实际上这里的x的数据范围就是−10^9≤x≤10^9,但可以理解为无限)
再聊聊什么叫映射
所谓映射:就是对应关系,可以简单的理解成用一个东西A代替另一个东西B,当你找到A的时候,可以理解成找到了B。
举个例子,我们把苹果映射成字母A,香蕉映射成字母B,那么我们在聊A的时候,相当于在聊苹果,我们在聊B的时候,相当于在聊香蕉。
再说说为什么离散化?
很简单的原因是我们无法开辟如此大的数组满足坐标上的关系。
如果我们想开辟数组,记录下数轴上的每一个点,方便我们想要给坐标上某个点加值的候直接加到数组上,我们需要开辟一个数组大小为2×10^9个int的数组。
但是
1Mb==1024kb==102410^3Byte
1 int =4 byte
也就是说1MB最多开1024×10^3/4==256000个int
x的范围是−10^9≤x≤10^9,那么假设我们开这么大的数组
我们开210^9个int就要210^9/(1024×10^3/4)个MB(或者写成210^9/256000个MB)
计算得7812.5MB,实际上题里最多只给了64MB。完全不可能。
如果的你懒得看计算,那我直接告诉你吧!64MB最多存开大约10^7个数组。
这就是我们为什么要离散化的原因。
那么,怎么离散化?
我们之前说过,离散化就是把无限个(很多很多个or超级多个)个体中,有限的个体映射到有限的空间中去。我们能读进来的数n是有限个,也就是说,我们只需要计算在无限长的坐标内有限个的点数,有限个是多少个呢?就是n个。n的取值范围是1≤n≤10^5,那么我们就把我们每一个读到的坐标先放到一个数组里面,进行一个排序,我们得到了有序的一个数组,这个数组里面存放着我们想要操作的坐标,也就是每次读进来的x,现在他是有序的,我们通过这个有序数组的下标,来映射这个读入的x。
eg:
我目前处理的数轴上的坐标x是 1,80,2,8,3000。
我把它存入到数组(vector容器)里面,并且排序他(sort),那么他们会变成
1,2,8,80,3000
他们的下标是
我们通过他们的下标的映射的值,来再建立一个数组,用于记录他们每个人加了多少数,也就是来记录+c。
eg:
上面的“8”这个坐标上x的位置想要+c比如说+ 12,那么由于8映射到的是下标2,那么我们就给另一个数组(假设另一个数组是a)的a[2]+=12(a初始化为全局变量。开始为0,+=12是为了考虑之后可能还会再在该坐标上加值,要累计一下)
但是
10^5的数量级还是太大了,我们必须再做优化。
为什么说10^5还大?
因为假设我有m=10^5个询问,我每次在前面都进行n=10^5个操作,也就是说我给10^5个数都加上了值,那么我在进行每一次询问的求和的时候,我一次询问求和就需要执行10^5次(n的操作数),我一共10^5个询问,就需要执行10^10次,but c++1秒通常最多跑1亿次(10^8)所以一定TLE掉了。
所以我们要用前缀和 做预处理。
预处理知识这里不详细展开,本文为叙述尽可能详细已经较长。
预处理之后我们再对询问进行映射,找到询问所对应的映射的区间
eg: 我们读入的值还是1,80,2,8,3000,前面为了解释映射,我们并没有引入读入的询问的映射,所以我们这里将坐标轴上想要加入的值 1,80,2,8,3000和询问的值:7,87的映射一并说起,实际上,我们是将要映射的值,全部存入到一个变长数组vector里面,再根据vector数组的排序来进行映射。
假设vector数组为adds
那么adds里面的应该有的值是1,80,2,8,3000以及两个待询问的值,7,87
假设读入1,80,2,8,3000,询问的值为7,87,
那么我们先排序,得到对应的数值大小,根据数值的大小去映射他们的下标。
我们之前已经通过前缀和处理了读入的值,所以此时直接输出数组的询问即可。
聊聊细节:
实际上对于数组询问的存储是需要定义一个pair的。
因为是一对儿嘛。
所以说处理询问的输出的时候需要做一个范围遍历
for (auto item : query)
{
int l = find(item.first), r = find(item.second);//分别求出离散化之后的值,直接根据离散化后的l和r找到
cout << s[r] - s[l - 1] << endl;
}
至于find函数,是进行离散化的一个函数。这个函数是需要自己实现的,我们前面所说的一切想要求对应某个x轴上面的坐标都是要通过find函数来对其进行离散化
int find(int x)//求一下x的值离散化后的结果,或说用于离散化。(二分法)
{
int l = 0, r = alls.size() - 1;//确定下标范围。最小为0,最大就是all.size()-1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
find的函数的实现是通过二分法来实现的。我们先将所有下标,无论是想要+c坐标的点x,还是想要查询的l,r两个点都放入到一个alls的vector数组里面,通过排序这个alls数组,我们得到了他们所有坐标的相对大小关系。1,80,2,8,3000,7,87。
排序得到 1,2,7,8,87,3000再通过二分,将他们的下标存到另一个数组(我们定义为a数组)里面,a数组就真正的存放着所有离散化后的坐标,想查询的,想修改的,都在里面。
我们修改时就在a里面修改,查询时就通过a的前缀和,放另一个数组s里面,来求l,r的所有范围。
感谢观看。
Thanks for watch.❤
Your illustration is the pink of perfection .
很棒,但是好像没有涉及到去重的细节