【线段树】2276. 统计区间中的整数数目

2024-04-12 07:52
文章标签 统计 整数 区间 线段 数目 2276

本文主要是介绍【线段树】2276. 统计区间中的整数数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

本文涉及知识点

线段树

LeetCode2276. 统计区间中的整数数目

给你区间的 空 集，请你设计并实现满足要求的数据结构：
新增：添加一个区间到这个区间集合中。
统计：计算出现在 至少一个 区间中的整数个数。
实现 CountIntervals 类：
CountIntervals() 使用区间的空集初始化对象
void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
int count() 返回出现在 至少一个 区间中的整数个数。
注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。
示例 1：
输入
[“CountIntervals”, “add”, “add”, “count”, “add”, “count”]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出
[null, null, null, 6, null, 8]
解释
CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象
countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中
countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
countIntervals.count(); // 返回 6
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 7、8、9、10 出现在区间 [7, 10] 中
countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中
countIntervals.count(); // 返回 8
// 整数 2 和 3 出现在区间 [2, 3] 中
// 整数 5 和 6 出现在区间 [5, 8] 中
// 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
// 整数 9 和 10 出现在区间 [7, 10] 中
提示：
1 <= left <= right <= 109
最多调用 add 和 count 方法 总计 105 次
调用 count 方法至少一次

线段树

由于本题无法离散化，所以用数组内存必定会超，只能用哈希映射或二叉树动态开点，二叉树的性能略好，就用二叉树。就算用二叉树也刚刚能过。
区间修改，查询全部。
由于只用到了查询全部，所以查询可以不实现。
save 记录 整个区间 在题目所在区间的数量。
叶子save 的值为1，表示在至少一个区间。0，表示不在任何区间。

template<class TSave=int, class TRecord =int >
class CMyTreeRangeLineTree : public CTreeRangeLineTree<TSave, TRecord>
{	
public:using CTreeRangeLineTree<TSave, TRecord>::CTreeRangeLineTree;
protected:virtual void OnQuery(TSave& save) override{}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;}
};

本题只会更新1，如果需要考虑取消，也就是更新为0。需要将懒标记的默认值设置成-1。
CountIntervals():m_treeLine(1,1’000’000’000,0,-1){

}

代码

template<class TSave, class TRecord >
class CRangUpdateLineTree 
{
protected:virtual void OnQuery(TSave& save) = 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);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;
protected:virtual void OnQuery(TSave& save) override{}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 CountIntervals {
public:CountIntervals():m_treeLine(1,1'000'000'000,0,0){}void add(int left, int right) {m_treeLine.Update(left, right,1);}int count() {return m_treeLine.QueryAll();}CMyTreeRangeLineTree<> m_treeLine;
};

测试用例

CountIntervals countIntervals ; // 用一个区间空集初始化对象countIntervals.add(2, 3);  // 将 [2, 3] 添加到区间集合中countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中auto res = countIntervals.count();    // 返回 6// 整数 2 和 3 出现在区间 [2, 3] 中// 整数 7、8、9、10 出现在区间 [7, 10] 中Assert(6, res);countIntervals.add(5, 8);  // 将 [5, 8] 添加到区间集合中res = countIntervals.count();    // 返回 8// 整数 2 和 3 出现在区间 [2, 3] 中// 整数 5 和 6 出现在区间 [5, 8] 中// 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中// 整数 9 和 10 出现在区间 [7, 10] 中Assert(8, res);

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

这篇关于【线段树】2276. 统计区间中的整数数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/896546。

相关文章

Pandas中统计汇总可视化函数plot()的使用

Pandas中统计汇总可视化函数plot()的使用

《Pandas中统计汇总可视化函数plot()的使用》Pandas提供了许多强大的数据处理和分析功能,其中plot()函数就是其可视化功能的一个重要组成部分,本文主要介绍了Pandas中统计汇总可视化... 目录一、plot()函数简介二、plot()函数的基本用法三、plot()函数的参数详解四、使用pl
阅读更多...
Pandas统计每行数据中的空值的方法示例

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据（NaN值）是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值？为什么要统计空值？准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处
阅读更多...
Mysql如何将数据按照年月分组的统计

Mysql如何将数据按照年月分组的统计

《Mysql如何将数据按照年月分组的统计》：本文主要介绍Mysql如何将数据按照年月分组的统计方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql将数据按照年月分组的统计要的效果方案总结Mysql将数据按照年月分组的统计要的效果方案① 使用 DA
阅读更多...
使用C语言实现交换整数的奇数位和偶数位

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现：将一个整
阅读更多...
一文详解SQL Server如何跟踪自动统计信息更新

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中，我们都清楚统计信息对于优化器来说非常重要。一般情况下，我们会开启"自动更新
阅读更多...
opencv实现像素统计的示例代码

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量
阅读更多...
如何使用 Bash 脚本中的time命令来统计命令执行时间(中英双语)

如何使用 Bash 脚本中的time命令来统计命令执行时间(中英双语)

《如何使用Bash脚本中的time命令来统计命令执行时间(中英双语)》本文介绍了如何在Bash脚本中使用`time`命令来测量命令执行时间,包括`real`、`user`和`sys`三个时间指标,... 使用 Bash 脚本中的 time 命令来统计命令执行时间在日常的开发和运维过程中，性能监控和优化是不
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2