离散化

• 0. 概述
• 1. 离散化
  • 1.1. 基于二分
  • 1.2. 基于哈希表

0. 概述

• 上篇博客我们介绍了桶结构，假设现在给我们一个序列，数据范围是$[-10^9,10^9]$，显然我们是不能再用一个数组来存的

• 所以现在需要做的就是把大范围的数据映射到小范围数据，如：将$-123456789$映射到$5$，那么$a[5]=-123456789$，统计的时候直接$cnt[3]++$即可，这便是离散化

• 怎么快速的映射，并且让映射的数字相互之间不冲突？
  排序加去重，使序列升序的排到数组中

• 怎么找到映射后的数字在映射数组的下标？

  二分（已经排序了）、哈希表

1. 离散化

题目链接：802. 区间和 - AcWing题库

• 该题目的数据范围很大，但是数据的总数又比较小，在数轴上非常稀疏，并且如果用枚举的方式求区间和必定会超时，所以非常适合用离散化的思想来解决

1.1. 基于二分

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 必须要用离散化

const int N=3e5+10; // max(n+2m)=3e5,假设每次输入的值都不同,最大也才3e5个空间
int n,m; // n次在x位置上加c的操作,m次查询区间[l,r]所有数的和
int x,c;
int l,r;
int a[N]; // 存储数字
int s[N]; // 前缀和数组

// alls:需要离散化的数组,在插入和查询过程中把需要离散化的坐标添加进来
vector<int> alls; // 存储插入和查询操作中遇到的所有唯一坐标,然后排序用于索引
vector<PII> add,query; // 存储插入和查询操作的二元组

// 找第一个大于等于x的下标,答案在左边,因此需要用二分的第二个模板(压缩右边界)
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; // 返回的是顺序而不是下标
}

int main() {
	cin>>n>>m;
	while(n--) {
		scanf("%d%d",&x,&c);
		add.push_back({x,c});
		alls.push_back(x); // 需要离散化的数值大小
	}
	while(m--) {
		int l,r;
		scanf("%d%d",&l,&r);
		query.push_back({l,r});
		// 区间也需要离散化
		alls.push_back(l);
		alls.push_back(r);
	}
	// 离散化:先排序后去重(因为可能有多个操作在同一个点上)
	// 排序
	sort(alls.begin(),alls.end());
	// 去重,unique去除范围内的重复元素并返回新数组的末尾位置
	alls.erase(unique(alls.begin(),alls.end()),alls.end());
	// 执行前n次插入操作
	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];
	// 执行后m次询问区间和操作
	for(auto item:query) {
		int l=find(item.first);
		int r=find(item.second);
		cout<<s[r]-s[l-1]<<endl;
	}
	return 0;
}
/*
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
/*

1.2. 基于哈希表

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 二分查询下标的时间是O(nlogn),而哈希表只需要O(1)

const int N=3e5+5;

int n,m;
int x,c;
int l,r;

vector<int> alls; // 所有需要离散化处理的数值
vector<PII> add,query; // 存储插入操作和区间和查询操作的向量

unordered_map<int,int> mp; // 哈希表(注意手写哈希表更快)

int a[N],s[N]; // 映射后的数组和前缀和数组

int main() {
	cin>>n>>m;
	while(n--) {
		scanf("%d%d",&x,&c);
		alls.push_back(x);
		add.push_back({x,c});
	}
	while(m--) {
		scanf("%d%d",&l,&r);
		alls.push_back(l);
		alls.push_back(r);
		query.push_back({l,r});
	}
	// 离散化
	sort(alls.begin(),alls.end());
	alls.erase(unique(alls.begin(),alls.end()),alls.end());
	// 映射到下标
	for(int i=0;i<=alls.size()-1;i++) {
		mp[alls[i]]=i+1; // 映射到从下标1开始
	}
	// 执行n次add操作
	for(auto item:add) {
		int x=mp[item.first];
		a[x]+=item.second;
	}
	// 用映射后的值计算前缀和
	for(int i=1;i<=alls.size();i++) {
		s[i]=s[i-1]+a[i];
	}
	// 执行m次查询操作
	for(auto item:query) {
		l=mp[item.first];
		r=mp[item.second];
		cout<<s[r]-s[l-1]<<endl;
	}
	return 0;
}

打赏