一、算法描述
本篇文章介绍离散化。
什么是离散化?
-
对于一个数组 (a) 来说,他是升序的,其中数字范围很大,例如 (-10^9)~(10^9)。
-
但是,数字的个数很少,只有 (0)~(10^5)。
-
那么这种情况下就没有必要将数组开得很大从而导致浪费空间,而只需要将每一个数字进行映射,例如 (a) 数组为:(1、20、300、4000、50000),将其映射:(1->1,20->2,300->3,4000->4,50000->5)。
-
以上过程称之为离散化。
如何实现?
离散化的关键如下:
-
先存储所有需要离散化的数,然后进行排序,排序之后进行去重操作,因为不需要重复映射。
-
以下函数均为库函数,可以直接调用。
vector alls; //需要映射的所有数
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 > 1;
if (alls[mid]
如何实现 (unique) 函数?
-
假设数组为:(1) (1) (2) (2) (2) (3) (3) (4) (5) (6) (6) (7)
-
那么很明显留下来的数需要满足以下两个条件:
1、是第一个数(整个序列中)
2、与前一个数不相同 -
实现代码如下:
vector::iterator unique(vector &a)
{
int j = 0;
for (int i = 0; i
二、题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是 (0)。
现在,我们首先进行 (n) 次操作,每次操作将某一位置 (x) 上的数加 (c)。
接下来,进行 (m) 次询问,每个询问包含两个整数 (l) 和 (r),你需要求出在区间 ([l,r]) 之间的所有数的和。
输入格式
第一行包含两个整数 (n) 和 (m)。
接下来 (n) 行,每行包含两个整数 (x) 和 (c)。
再接下来 (m) 行,每行包含两个整数 (l) 和 (r)。
输出格式
共 (m) 行,每行输出一个询问中所求的区间内数字和。
数据范围
(−10^9≤x≤10^9,)
(1≤n,m≤10^5,)
(−10^9≤l≤r≤10^9,)
(−10000≤c≤10000)
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
三、题目来源
AcWing算法基础课-802.区间和
四、算法思路
-
这道题显然就属于离散化的题目,但是还有后续操作。
-
首先,要离散化的数字不仅只有 (x),还有查询操作中的 (l) 和 (r) ,所以要先将所有数据存储下来,并将需要离散化的数据存入 (alls) 数组中。
-
其次,进行离散化操作。
-
另外,执行在 (x) 上加入 (c) 的操作,显然需要找到 (x) 离散化后的位置,包括后续的 ([l, r]) 内的区间和也需要找到 (l) 和 (r) 离散化后的位置,所以需要写一个函数来专门查找离散化后的位置。
-
此外,在最后输出区间和之前,我们需要处理前缀和以降低时间复杂度。(不知道如何求前缀和可以通过合集查看之前的文章,一维前缀和。)这里注意数据范围,(x),(l),(r) 都是 (10^5) ,所以数组的范围应该开到 (3 * 10^5),并加 (10) ,以防止溢出。
-
最后,处理输出结果即可。
五、源代码
#include
#include
#include
using namespace std;
typedef pair PII;
const int N = 300010;
int n, m;
int a[N];
vector alls;
vector add, query;
int find(int x)
{
int l = 0, r = alls.size() - 1;
while (l > 1;
if (alls[mid] > n >> m;
for (int i = 0; i > x >> c;
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i > 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
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net