【线段树 有序映射】715. Range 模块

算法可以发掘本质,如:
一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二,有无限多1X2和2X1的骨牌,某个棋盘若干格子坏了,如何在没有坏的格子放足够多骨牌。
三,某个单色图,1表示前前景,0表示后景色。每次操作可以将一个1,变成0。如何在最少得操作情况下,使得没有两个1相邻(四连通)。
四,若干路人,有些人是熟人,如何选出最多的人参加实验。为了避免熟人影响实验的效果,参加的人不能是熟人。
一二是二分图的最大匹配,三是二分图的最小点覆盖,四是二分图最大独立集。 而这三者是等效问题。

本文涉及知识点

线段树 有序映射
线段树:就求一乐乎,难写。在超时的边缘。

LeetCode715. Range 模块

Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
实现 RangeModule 类:

RangeModule() 初始化数据结构的对象。
void addRange(int left, int right) 添加 半开区间 [left, right),跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时,应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时,才返回 true ,否则返回 false 。
void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。

示例 1:

输入
[“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]

解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true (区间 [10, 14) 中的每个数都正在被跟踪)
rangeModule.queryRange(13, 15); 返回 false(未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字)
rangeModule.queryRange(16, 17); 返回 true (尽管执行了删除操作,区间 [16, 17) 中的数字 16 仍然会被跟踪)

提示:
1 <= left < right <= 109
在单个测试用例中,对 addRange 、 queryRange 和 removeRange 的调用总数不超过 104 次

代码

template<class TSave, class TRecord >
class CRangUpdateLineTree 
{
protected:
	virtual void OnQuery(TSave& save, int iSaveLeft, int iSaveRight) = 0;
	virtual void OnUpdate(TSave& save, int iSaveLeft,int iSaveRight, const TRecord& update) = 0;
	virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
	virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0;
};


template<class TSave, class TRecord >
class CTreeRangeLineTree : public CRangUpdateLineTree<TSave, TRecord>
{
protected:
	struct CTreeNode
	{
		int Cnt()const { return m_iMaxIndex - m_iMinIndex + 1; }
		int m_iMinIndex;
		int m_iMaxIndex;
		TRecord record;
		TSave data;
		CTreeNode* m_lChild = nullptr, * m_rChild = nullptr;
	};
	CTreeNode* m_root;
	TSave m_tDefault;
	TRecord m_tRecordDef;
public:
	CTreeRangeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault,TRecord tRecordDef) {
		m_tDefault = tDefault;
		m_tRecordDef = tRecordDef;
		m_root = CreateNode(iMinIndex, iMaxIndex);
	}
	void Update(int iLeftIndex, int iRightIndex, TRecord value)
	{
		Update(m_root, iLeftIndex, iRightIndex, value);
	}
	TSave QueryAll() {
		return m_root->data;
	}
	void Query(int leftIndex, int leftRight) {
		Query(m_root, leftIndex, leftRight);
	}
protected:
	void Query(CTreeNode* node, int iQueryLeft, int iQueryRight) {
		if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) {
			this->OnQuery(node->data,node->m_iMinIndex,node->m_iMaxIndex);
			return;
		}
		if (1 == node->Cnt()) {//没有子节点
			return;
		}
		CreateChilds(node);
		Fresh(node);
		const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2;
		if (mid >= iQueryLeft) {
			Query(node->m_lChild, iQueryLeft, iQueryRight);
		}
		if (mid + 1 <= iQueryRight) {
			Query(node->m_rChild, iQueryLeft, iQueryRight);
		}
	}
	void Update(CTreeNode* node, int iOpeLeft, int iOpeRight, TRecord value)
	{
		const int& iSaveLeft = node->m_iMinIndex;
		const int& iSaveRight = node->m_iMaxIndex;
		if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
		{
			this->OnUpdate(node->data, iSaveLeft, iSaveRight, value);
			this->OnUpdateRecord(node->record, value);
			return;
		}
		if (1 == node->Cnt()) {//没有子节点
			return;
		}
		CreateChilds(node);
		Fresh(node);
		const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2;
		if (mid >= iOpeLeft) {
			this->Update(node->m_lChild, iOpeLeft, iOpeRight, value);
		}
		if (mid + 1 <= iOpeRight) {
			this->Update(node->m_rChild, iOpeLeft, iOpeRight, value);
		}
		// 如果有后代,至少两个后代
		this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data,node->m_iMinIndex,node->m_iMaxIndex);
	}
	void CreateChilds(CTreeNode* node) {
		if (nullptr != node->m_lChild) { return; }
		const int iSaveLeft = node->m_iMinIndex;
		const int iSaveRight = node->m_iMaxIndex;
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		node->m_lChild = CreateNode(iSaveLeft, mid);
		node->m_rChild = CreateNode(mid + 1, iSaveRight);
	}
	CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) {
		CTreeNode* node = new CTreeNode;
		node->m_iMinIndex = iMinIndex;
		node->m_iMaxIndex = iMaxIndex;
		node->data = m_tDefault;
		node->record = m_tRecordDef;
		return node;
	}
	void Fresh(CTreeNode* node)
	{
		if (m_tRecordDef == node->record)
		{
			return;
		}
		CreateChilds(node);
		Update(node->m_lChild, node->m_lChild->m_iMinIndex, node->m_lChild->m_iMaxIndex, node->record);
		Update(node->m_rChild, node->m_rChild->m_iMinIndex, node->m_rChild->m_iMaxIndex, node->record);
		node->record = m_tRecordDef;
	}
};

template<class TSave=int, class TRecord =int >
class CMyTreeRangeLineTree : public CTreeRangeLineTree<TSave, TRecord>
{	
public:
	using CTreeRangeLineTree<TSave, TRecord>::CTreeRangeLineTree;
	bool queryRange(int left, int right) {
		m_bHas = true;
		CTreeRangeLineTree<TSave, TRecord>::Query(left, right);
		return m_bHas;
	}
protected:
	bool m_bHas = true;
	virtual void OnQuery(TSave& save, int iSaveLeft, int iSaveRight) override
	{
		m_bHas &= (save == (iSaveRight - iSaveLeft + 1));
	}
	virtual void OnUpdate(TSave& save, int iSaveLeft, int iSaveRight, const TRecord& update) override
	{ 
		save = update*(iSaveRight-iSaveLeft+1);
	}
	virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
	{
		par = left + r;
	}
	virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
	{
		old = newRecord;
	}
};

class RangeModule {
public:
	RangeModule() :m_treeLine(1, 1'000'000'000, 0, -1) {

	}

	void addRange(int left, int right) {
		m_treeLine.Update(left, right-1, 1);
	}

	bool queryRange(int left, int right) {
		return m_treeLine.queryRange(left, right - 1);
	}

	void removeRange(int left, int right) {
		m_treeLine.Update(left, right-1, 0);
	}
	CMyTreeRangeLineTree<> m_treeLine;
};

有序映射

class RangeModule {
public:
	RangeModule() {

	}

	void addRange(int left, int right) {
		auto it1 = m_mLeftRight.lower_bound(left);
		auto it2 = m_mLeftRight.upper_bound(right);
		if (it1 != m_mLeftRight.begin())
		{
			auto tmp = it1;
			--tmp;
			if (tmp->second >= left)
			{
				left = tmp->first;
				--it1;
			}
		}
		if (it2 != m_mLeftRight.begin())
		{
			auto tmp = it2;
			--tmp;
			if (tmp->second > right)
			{
				right = tmp->second;
			}
		}
		m_mLeftRight.erase(it1, it2);
		m_mLeftRight[left] = right;
	}

	bool queryRange(int left, int right) {
		auto it1 = m_mLeftRight.upper_bound(left);
		if (it1 != m_mLeftRight.begin())
		{
			auto tmp = it1;
			tmp--;
			return tmp->second >= right;
		}
		return false;
	}

	void removeRange(int left, int right) {
		auto it1 = m_mLeftRight.lower_bound(left);
		auto it2 = m_mLeftRight.upper_bound(right);
		int iNewLeft = -1;
		if (it1 != m_mLeftRight.begin())
		{
			auto tmp = it1;
			--tmp;
			if (tmp->second >= left)
			{
				iNewLeft = tmp->first;
			}
		}
		int iNewRight = -1;
		if (it2 != m_mLeftRight.begin())
		{
			auto tmp = it2;
			--tmp;
			if (tmp->second > right)
			{
				iNewRight = tmp->second;
			}
		}
		m_mLeftRight.erase(it1, it2);
		if (-1 != iNewLeft)
		{
			m_mLeftRight[iNewLeft] = left;
		}
		if (-1 != iNewRight)
		{
			m_mLeftRight[right] = iNewRight;
		}
	}
	std::map<int, int> m_mLeftRight;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业

。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙,那算法就是他的是睛|

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/537484.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

谷歌pixel6/7pro等手机WiFi不能上网,显示网络连接受限

近期在项目中遇到一个机型出现的问题,先对项目代码进行排查,发现别的设备都能正常运行,就开始来排查机型的问题,特意写出来方便后续查看,也方便其它开发者来自查。 设备机型:Pixel 6a 设备安卓版本:13 该方法无需root,只需要电脑设备安装adb(即Android Debug Bridge…

计算机网络---第九天

以太网交换机的工作原理 以太网定义&#xff1a; 定义&#xff1a;输出标准Ethernet2类型帧的网络 以太网特征&#xff1a; 特征&#xff1a;多路访问&#xff0c;广播式的网络 mac地址: 每台设备都有一个唯一的物理地址&#xff0c;全球唯一 48位长度&#xff0c;16禁止…

数显IC/点阵数显驱动芯片/抗干扰数显驱动-VK1Q60 QFN16L 8×4点阵

产品品牌&#xff1a;永嘉微电/VINKA 产品型号&#xff1a;VK1Q60 封装形式&#xff1a;QFN16L 概述 VK1Q60是一种带键盘扫描电路接口的 LED 驱动控制专用芯片&#xff0c;内部集成有数据锁存 器、LED 驱动、键盘扫描等电路。SEG脚接LED阳极&#xff0c;GRID脚接LED阴极&…

GPT-4 Turbo with Vision 提高‮写了‬作、数学、逻‮推辑‬理和编码能力

新版 GPT-4 Turbo 今‮开天‬始现‮向已‬所有付费 ChatGPT 用‮开户‬放。GPT-4 Turbo提高‮写了‬作、数学、逻‮推辑‬理和编码能力。具有128k上下文窗口&#xff0c;可以处理超过300页的文本&#xff0c;输出‮度速‬更快。 现‮已在‬经开始‮续陆‬推送&#xff0c;如果…

「seata」分布式事务seata部署及应用

「seata」分布式事务seata部署及应用 seata 版本一、部署seata服务1、配置config.txt文件中的属性值2、为seata服务单独创建一个nacos命名空间3、利用脚本上传配置文件到nacos4、配置seata服务的application.yml6、执行数据库脚本5、使用脚本启动seata服务 二、配置并启动微服务…

品牌发言稿怎么写?媒介盒子分享

品牌发言稿的重要性不言而喻&#xff0c;它不仅代表着品牌形象&#xff0c;更是沟通品牌与消费者、合作伙伴的桥梁。如何撰写一篇高质量的品牌发言稿&#xff0c;成为许多品牌关注的焦点。今天媒介盒子来和大家聊聊&#xff1a;品牌发言稿怎么写。 一、 发言稿写作技巧 1.结构…

MQTT的学习

近期构建物联网平台&#xff0c;学习到MQTT&#xff0c;这里使用的是uniapp作为连接MQTT broker的&#xff0c;这里使用的是国产的EMQX。 MQTT的认识 MQTT 协议入门&#xff1a;基础知识和快速教程 | EMQ&#xff08;简单的认识&#xff09; 创建 MQTT 连接时如何设置参数&am…

UI自动化测试案例

备注:本文为博主原创文章,未经博主允许禁止转载。如有问题,欢迎指正。 个人笔记(整理不易,有帮助,收藏+点赞+评论,爱你们!!!你的支持是我写作的动力) 笔记目录:笔记本~笔记目录_airtest和selenium那个好用-CSDN博客 个人随笔:工作总结随笔_8、以前工作中都接触过哪…

如何应对app应用程序或者网站常见的几种攻击类型

大家好&#xff0c;我是咕噜铁蛋&#xff01;今天&#xff0c;我想和大家聊聊一个我们日常生活中经常遇到的问题——如何应对app或者网站常见的几种攻击类型。随着互联网的普及&#xff0c;app和网站已经成为我们获取信息、交流互动的重要平台。然而&#xff0c;这些平台也时常…

Vue.js组件精讲 第2章 基础:Vue.js组件的三个API:prop、event、slot

如果您已经对 Vue.js 组件的基础用法了如指掌&#xff0c;可以跳过本小节&#xff0c;不过当做复习稍读一下也无妨。 组件的构成 一个再复杂的组件&#xff0c;都是由三部分组成的&#xff1a;prop、event、slot&#xff0c;它们构成了 Vue.js 组件的 API。如果你开发的是一个…

360AI搜索爆火,位居三月全球AI新品增速榜榜首

近日&#xff0c;独立AI产品榜单“AI产品榜&#xff08;aicpb.com&#xff09;”发布最新全球AI新品增速榜单&#xff0c;该榜单数据显示&#xff0c;360AI搜索位居三月新品增速榜榜首&#xff0c;3月访问量环比增加1798.76%。360集团另一款AI产品360苏打办公也同时上榜&#x…

【2024年认证杯】A题详细思路+数据(来源)+成品论文+模型代码(matlab+python)

2024年认证杯A题 解题思路 ⭐⭐第一问题分析第二问题分析第三问题分析 数据与数据来源&#x1f389;&#x1f389;指标解释数据来源 成品参考论文&#x1f60a;&#x1f60a;python/ matlab 代码&#x1f680;&#x1f680; 解题思路 ⭐⭐ 这个题目要求我们围绕人造保暖纤维的…

Excel表格中的10000元变成1万元

程序代码园发文地址&#xff1a;Excel表格中的10000元变成1万元-程序代码园小说,Java,HTML,Java小工具,程序代码园,http://www.byqws.com/ ,Excel表格中的10000元变成1万元http://www.byqws.com/blog/3149.html?sourcecsdn 今天早上有同事问我&#xff0c;在Excel表格里面怎么…

Vue项目中,使用高级表格vxe-table中的【vxe-grid】动态列之动态插槽

1、首先项目当中得安装了vxe-table // 没有安装的话&#xff0c;可以使用一下命令安装 npm install vxe-table 或 yarn add vxe-table使用示例&#xff1a; import Vue from vue import VXETable from vxe-table import vxe-table/lib/style.cssVue.use(VXETable)2、动态列中动…

直播预告:告诉你最真实的网优行业内幕!

很多小伙伴在后台私信小编&#xff0c;说想学网优但是从来没接触过这一行&#xff0c;或者是接触过但是了解不多&#xff0c;零基础真的可以学吗&#xff1f;免费试学时间是多久&#xff1f;学完后有多少薪资&#xff1f;上课的方式是什么&#xff1f;需不需要出差&#xff1f;…

MySQL高可用搭建方案MHA

MHA架构介绍 MHA是Master High Availability的缩写&#xff0c;它是目前MySQL高可用方面的一个相对成熟的解决方案&#xff0c;其核心是使用perl语言编写的一组脚本&#xff0c;是一套优秀的作为MySQL高可用性环境下故障切换和主从提升的高可用软件。在MySQL故障切换过程中&am…

Python实现BOA蝴蝶优化算法优化随机森林分类模型(RandomForestClassifier算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后获取。 1.项目背景 蝴蝶优化算法(butterfly optimization algorithm, BOA)是Arora 等人于2019年提出的一种元启发式智能算…

React之基础项目搭建

前言 React的生态系统非常庞大&#xff0c;拥有大量的第三方库和工具&#xff0c;如React Native&#xff08;用于构建原生移动应用&#xff09;、Next.js&#xff08;用于构建服务器渲染应用&#xff09;、Create React App&#xff08;用于快速搭建React应用的脚手架&#x…

【Linux】网络编程套接字二

网络编程套接字二 1.TCP网络编程1.1TCP Server服务端1.2 TCP Client客户端 2.Server 多进程版本2.1普通版2.2 信号版 3.Server 多线程版4.Server 线程池版5.日志函数重新设计6.守护进程7.TCP协议通讯流程8.TCP和UDP 对比 喜欢的点赞&#xff0c;收藏&#xff0c;关注一下把&…

蓝桥杯真题Day48 倒计时5天 练了几道真题小程序+回溯剪枝应用一个小程序

[蓝桥杯 2023 省 A] 更小的数 题目描述 小蓝有一个长度均为 n 且仅由数字字符 0∼9 组成的字符串&#xff0c;下标从0到 n−1&#xff0c;你可以将其视作是一个具有n位的十进制数字num&#xff0c;小蓝可以从num 中选出一段连续的子串并将子串进行反转&#xff0c;最多反转一次…