离散化 | OI笔记

有序整数序列的离散化

含义：
将大整数映射成小整数并存储的过程，称之为整数离散化，整数离散化具有数值跨度大，但在数组中的分布稀疏的特点
注意：对于待离散化的整数序列，其值必须是有序的，而对于离散之后的新序列，仍保持着原数组中数的顺序

需要解决的问题：
1.对于原整数序列中有重复元素时如何映射————利用unique去重函数

unique函数：
将序列中所有重复的元素去重，并且返回去重之后新数组的尾端点。

对数组进行unique去重处理后，剩余的重复元素会被保留在序列最后的位置，所以需要使用erase函数清空这些重复的值。

2.如何在最小的时间复杂度内计算出原整数序列中的数离散化后的值
解决方式：

vector<int> alls;
// 存储所有待离散化的值

sort(alls.begin(), alls.end())
// 对alls序列进行排序

alls.erase(unique(alls.begin(), alls.end())alls.end);
// 对alls序列进行去重

int find(int x)
{
    int l = 0; r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] > x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
    // 加 1 意为从数组下标的 1 处开始映射，好处是可以方便前缀和的计算
}

例题：
Acwing802 - 区间和

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 300000;
// n和m的数据范围都是1e5， 那么所有坐标的和为3 * 1e5

typedef pair<int, int> ope; // 定义二元组，分别表示对序列的操作

int a[N + 10]; // 离散化之后的序列
int s[N + 10]; // 离散化之后序列的前缀和
vector<int> alls; // 用于存储待离散化的值
vector<ope> add, access; // 对原序列进行的操作（加，访问）

int find(int x)
{
	int l = 0, r = alls.size() - 1;
	while(l < r)
	{
		int mid = r + l >> 1;
		if (alls[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return r + 1;
	// 从1开始将所有的数进行映射，为了方便前缀和的计算
}
// 找到x离散化后的结果
 
int main()
{
	int n, m;
	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;
		access.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 ++)
		s[i] = s[i - 1] + a[i];
	// 计算序列的前缀和
	
	for (auto item : access)
	{
		int l = find(item.first), r = find(item.second);
		cout << s[r] - s[l - 1] << endl;
	}
	return 0;
	
}