离散化
一、算法描述
本篇文章介绍离散化。
什么是离散化?
-
对于一个数组 \(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<int> 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 < r)
{
int mid = (l + r + 1) >> 1;
if (alls[mid] <= x) l = mid;
else r = mid - 1;
}
return r;
}
如何实现 \(unique\) 函数?
-
假设数组为:\(1\) \(1\) \(2\) \(2\) \(2\) \(3\) \(3\) \(4\) \(5\) \(6\) \(6\) \(7\)
-
那么很明显留下来的数需要满足以下两个条件:
1、是第一个数(整个序列中)
2、与前一个数不相同 -
实现代码如下:
vector<int>::iterator unique(vector<int> &a)
{
int j = 0;
for (int i = 0; i < a.size(); ++i)
if (!i || a[i] != a[i - 1])
a[j ++ ] = a[i];
return a.begin() + j;
}
二、题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是 \(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
三、题目来源
四、算法思路
-
这道题显然就属于离散化的题目,但是还有后续操作。
-
首先,要离散化的数字不仅只有 \(x\),还有查询操作中的 \(l\) 和 \(r\) ,所以要先将所有数据存储下来,并将需要离散化的数据存入 \(alls\) 数组中。
-
其次,进行离散化操作。
-
另外,执行在 \(x\) 上加入 \(c\) 的操作,显然需要找到 \(x\) 离散化后的位置,包括后续的 \([l, r]\) 内的区间和也需要找到 \(l\) 和 \(r\) 离散化后的位置,所以需要写一个函数来专门查找离散化后的位置。
-
此外,在最后输出区间和之前,我们需要处理前缀和以降低时间复杂度。(不知道如何求前缀和可以通过合集查看之前的文章,一维前缀和。)这里注意数据范围,\(x\),\(l\),\(r\) 都是 \(10^5\) ,所以数组的范围应该开到 \(3 * 10^5\),并加 \(10\) ,以防止溢出。
-
最后,处理输出结果即可。
五、源代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N];
vector<int> alls;
vector<PII> add, query;
int find(int x)
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (alls[mid] <= x) l = mid;
else r = mid - 1;
}
return r + 1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
int x, c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; ++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) a[i] += a[i - 1];
for (auto item : query)
{
int l = find(item.first), r = find(item.second);
cout << a[r] - a[l - 1] << endl;
}
return 0;
}
热门相关:试婚老公,用点力! 娇妻太甜:老公,要抱抱 绍宋 至尊剑皇 跟总裁假结婚的日子