离散化

一、算法描述

本篇文章介绍离散化。

什么是离散化?

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

三、题目来源

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

热门相关:试婚老公,用点力!   娇妻太甜:老公,要抱抱   绍宋   至尊剑皇   跟总裁假结婚的日子