离散化

2023-11-22 15:07 由 grave-master 发表于 #其他

一、算法描述

本篇文章介绍离散化。

什么是离散化？

对于一个数组 \(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\)

输入样例：

输出样例：

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 <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;
}