基础算法模板之区间离散化与合并()-其他

基础算法模板之区间离散化与合并()

区间离散化

将数量很少但数值很大的区间下标有序映射到一个集中的区间内，并可以根据原下标x迅速找到(二分)新下标

vector<int> alls; // 存储所有可能下标
sort(alls.begin(),alls.end()); // 排序
alls.erase(unique(alls.begin(),alls,end()),alls.end()); // 有序序列去重
// 根据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 l + 1; // 保证映射后的下标是从1开始
}

区间合并

区间合并是将多段区间中有交集的区间合并成一段区间

void merge(vector<pair<int,int>> &segs)
{
	vector<pair<int,int>> res;
	int st = -2e9,ed = -2e9;
	for(auto seg : segs)
	{
		if(ed < seg.first)
		{
			if(st != -2e9) res.push_back({st,ed});
			st = seg.first;
			ed = seg.second;
		}
		else
		{
			ed = max(ed,seg.second);
		}
	}
	if(st != -2e9) res.push_back({st,ed});
	segs = res;
}

区间离散化

将数量很少但数值很大的区间下标有序映射到一个集中的区间内，并可以根据原下标x迅速找到(二分)新下标

vector<int> alls; // 存储所有可能下标
sort(alls.begin(),alls.end()); // 排序
alls.erase(unique(alls.begin(),alls,end()),alls.end()); // 有序序列去重
// 根据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 l + 1; // 保证映射后的下标是从1开始
}

区间合并

区间合并是将多段区间中有交集的区间合并成一段区间

void merge(vector<pair<int,int>> &segs)
{
	vector<pair<int,int>> res;
	int st = -2e9,ed = -2e9;
	for(auto seg : segs)
	{
		if(ed < seg.first)
		{
			if(st != -2e9) res.push_back({st,ed});
			st = seg.first;
			ed = seg.second;
		}
		else
		{
			ed = max(ed,seg.second);
		}
	}
	if(st != -2e9) res.push_back({st,ed});
	segs = res;
}