离散化

⬅ 返回

1、思路

离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。

做法是是对原来的数轴下标进行排序，再去重，之后通过二分查找确定在新数组中的位置。

本质也就是将老坐标(太大) 映射到 新坐标(小)

2、例题

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

3、代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
vector<pair<int,int>> add,query;//add储下标和值  query储存要求的l,r
vector<int> alls;//alls记录所有的坐标
int a[N];
int s[N];
 
int find(int t)//把老元素t映射出在新坐标中的下标
{
	int l=0,r=alls.size()-1;
	while(l<r)//通过二分
	{
		int mid = (l+r)/2;
		if(alls[mid]>=t)
			r=mid;
		else
			l=mid+1;
	}
	return l;
}
 
 
int main(){
 
	int n,m;
	cin>>n>>m;
	while(n--)
	{
		int x,c;
		cin>>x>>c;
		add.push_back({x,c});
		alls.push_back(x);
	}
	while(m--)
	{
		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 dit:add)
	{
		int t = find(dit.first)+1;
		a[t]+=dit.second;
	}
	
	for(int i=1;i<=alls.size();i++)
	{
		s[i]=s[i-1]+a[i];//前缀和
	}
	
	for(auto dit:query)
	{
		int l = find(dit.first)+1;
		int r = find(dit.second)+1;
		cout<<s[r]-s[l-1]<<endl;	
	}
}
 

4、本题知识点

1、STL

第一部分：vector<pair<int,int>> 的使用

第二部分：sort方法的使用以及去重的方法

第三部分：遍历for(auto dit:query)

#include <vector>
vector<pair<int,int>> add,query;//add储下标和值  query储存要求的l,r
vector<int> alls;//alls记录所有的坐标
add.push_back({x,c});
alls.push_back(x);
----------------------------------------------------------------------------------
#include <algorithm>
sort(alls.begin(),alls.end());//排序
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重
---------------------------------------------------------------------------------
for(auto dit:query)
	{
		int l = find(dit.first)+1;
		int r = find(dit.second)+1;
		cout<<s[r]-s[l-1]<<endl;	
	}

2、二分

3、前缀和