POJ2777：线段树的懒惰更新策略分析与实现

作者：灰灰t2502911555 | 来源：互联网 | 2024-11-03 15:22

题目链接：POJ2777。问题描述：给定一个区域，需要进行多次涂色操作，并在每次操作后查询某个区间内的不同颜色数量。解决方案：由于题目中颜色种类不超过30种，可以利用线段树的懒惰更新策略来高效处理这些操作。通过懒惰标记，避免了不必要的节点更新，从而显著提高了算法的效率。此外，该方法还能有效应对大规模数据输入，确保在合理的时间内完成所有操作。

题目链接&＃xff1a; poj 2777

题意&＃xff1a;板块涂色&＃xff0c;询问区间内颜色的数目。

解题&＃xff1a;因为题目给出颜色数目最多30种&＃xff0c;因此可以借用二进制中的或运算来更新父区间。但是这写的是线段树常用的懒人标记------延迟更新。

别人已经写的很好了&＃xff0c;直接借用吧&＃xff0c;博客链接 https://blog.csdn.net/Tong_zhi/article/details/82683219

言下之意就是当遇到的区间&＃xff0c;已经被包含在更新区间内&＃xff0c; 如果按照常规的思路&＃xff0c;那么就是继续遍历到叶结点&＃xff0c;一一进行修改&＃xff0c;但是这样很浪费时间。

这里借用了懒标记&＃xff0c;也就是对这种纯区间&＃xff08;区间内的元素都需要更改成某值&＃xff09;&＃xff0c;我们只需要对他加一个标记。当下次更新或者询问的时候再进行修改。

修改操作&＃xff1a; 先将自己的标记赋值给左右儿子&＃xff0c;然后取消自己的标记&＃xff0c;对于左右儿子的标记&＃xff0c;也一样当下次更新或者询问的时候再进行修改。

下推操作&＃xff08;懒标记&＃xff09;&＃xff1a;

void pushdown(int rt)
{if (tree[rt].lazy){tree[rt<<1].col&＃61;tree[rt<<1|1].col&＃61;tree[rt].lazy;tree[rt<<1].lazy&＃61;tree[rt<<1|1].lazy&＃61;tree[rt].lazy;tree[rt].lazy&＃61;0;}return ;
}

AC代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Mem0(x) memset(x,0,sizeof(x))
#define Mem1(x) memset(x,-1,sizeof(x))
#define MemX(x) memset(x,0x3f,sizeof(x))
using namespace std;
typedef long long ll;
const int inf&＃61;0x3f3f3f;
const double pi&＃61;acos(-1.0);const int MAXN&＃61;1e5&＃43;10;
struct s{int l,r;ll col,lazy;
}tree[MAXN<<2];
int l,t,o;//长度&＃xff0c;颜色数&＃xff0c;询问次数
ll ans;
void btree(int rt,int l,int r)
{tree[rt].l&＃61;l;tree[rt].r&＃61;r;tree[rt].lazy&＃61;0;tree[rt].col&＃61;1;if (l&＃61;&＃61;r){return ;}int mid&＃61;(l&＃43;r)>>1;btree(rt<<1,l,mid);btree(rt<<1|1,mid&＃43;1,r);return ;
}
void pushdown(int rt)
{if (tree[rt].lazy){tree[rt<<1].col&＃61;tree[rt<<1|1].col&＃61;tree[rt].lazy;tree[rt<<1].lazy&＃61;tree[rt<<1|1].lazy&＃61;tree[rt].lazy;tree[rt].lazy&＃61;0;}return ;
}
void update(int rt,int a,int b,int c)
{if (a>tree[rt].r||b<tree[rt].l){return ; }else if (a<&＃61;tree[rt].l&&tree[rt].r<&＃61;b){tree[rt].col&＃61;tree[rt].lazy&＃61;1<<(c-1);return ;}pushdown(rt);update(rt<<1,a,b,c);update(rt<<1|1,a,b,c);tree[rt].col&＃61;tree[rt<<1].col|tree[rt<<1|1].col;return ;
}
void query(int rt,int a,int b)
{if (a>tree[rt].r||b<tree[rt].l){return ;}else if (a<&＃61;tree[rt].l&&tree[rt].r<&＃61;b){ans|&＃61;tree[rt].col;return ;}pushdown(rt);query(rt<<1,a,b);query(rt<<1|1,a,b);return ;
}
ll find(ll a)
{int tmp&＃61;0;while (a){if (a%2&＃61;&＃61;1)tmp&＃43;&＃43;;a>>&＃61;1;}return tmp;
}
int main()
{scanf("%d%d%d",&l,&t,&o); btree(1,1,l);while (o--){char str;int a,b,c;cin>>str;if (str&＃61;&＃61;&＃39;C&＃39;){scanf("%d%d%d",&a,&b,&c);update(1,a,b,c);}else{scanf("%d%d",&a,&b);ans&＃61;0;if (a>b)query(1,b,a);else query(1,a,b);cout<endl;}}return 0;
}

转:https://www.cnblogs.com/q1204675546/p/11221097.html

推荐阅读

go
线段树详解与实现

本文详细介绍了线段树的基本概念及其在编程竞赛中的应用，并提供了一个具体的线段树实现代码示例。 ... [详细]

蜡笔小新 2024-11-19 21:26:45
const
SDOI2008 Cave Exploration - 动态树结构应用

题目编号：2049 [SDOI2008]Cave Exploration。题目描述了一种动态图操作场景，涉及三种基本操作：断开两个节点间的连接（destroy(a,b)）、建立两个节点间的连接（connect(a,b)）以及查询两节点是否连通（query(a,b)）。所有操作均确保图中无环存在。 ... [详细]

蜡笔小新 2024-11-18 20:11:35
const
编译原理中的语法分析方法探讨

本文探讨了在编译原理课程中遇到的复杂文法问题，特别是当使用SLR(1)文法时遇到的多重规约与移进冲突。文章讨论了可能的解决策略，包括递归下降解析、运算符优先级解析等，并提供了相关示例。 ... [详细]

蜡笔小新 2024-11-19 14:44:19
const
HDU2757 海洋洋流（BFS+优先队列）

题目描述：计算从起点到终点的最小能量消耗。如果下一个单元格的风向与当前单元格相同，则消耗为0，否则为1。共有8个可能的方向。 ... [详细]

蜡笔小新 2024-11-18 16:02:40
const
洛谷 P4009 汽车加油行驶问题解析

探讨了经典算法题目——汽车加油行驶问题，通过网络流和费用流的视角，深入解析了该问题的解决方案。本文将详细阐述如何利用最短路径算法解决这一问题，并提供详细的代码实现。 ... [详细]

蜡笔小新 2024-11-21 14:21:38
go
NYOJ20：吝啬的国度 - 图的DFS算法解析

本文详细解析了NYOJ20 - 吝啬的国度问题，通过图的深度优先搜索（DFS）算法解决路径查询问题。 ... [详细]

蜡笔小新 2024-11-17 15:53:45
go
开发笔记:1035 Password (20)

开发笔记:1035 Password (20) ... [详细]

蜡笔小新 2024-11-16 19:33:06
const
无向图中的最小环问题

本问题涉及在给定的无向图中寻找一个至少包含三个节点的环，该环上的节点不重复，并且环上所有边的长度之和最小。目标是找到并输出这个最小环的具体方案。 ... [详细]

蜡笔小新 2024-11-21 15:01:34
future
Ryanair Expands Frankfurt Operations, Challenges Lufthansa's Dominance

Irish budget airline Ryanair announced plans to significantly increase its route network from Frankfurt Airport, marking a direct challenge to Lufthansa, Germany's leading carrier. ... [详细]

蜡笔小新 2024-11-21 13:09:01
const
Qt中信号与槽机制对比传统回调函数的优势

在Qt框架中，信号与槽机制是一种独特的组件间通信方式。本文探讨了这一机制相较于传统的C风格回调函数所具有的优势，并分析了其潜在的不足之处。 ... [详细]

蜡笔小新 2024-11-20 10:48:37
copy
华为鲲鹏平台适配的Redis Docker镜像构建指南

本文详细介绍如何在华为鲲鹏平台上构建和使用适配ARM架构的Redis Docker镜像，解决常见错误并提供优化建议。 ... [详细]

蜡笔小新 2024-11-19 15:04:08
get
Java集合框架深入解析：HashSet详解

本文详细介绍了HashSet类，它是Set接口的一个实现，底层使用哈希表（实际上是HashMap实例）。HashSet不保证元素的迭代顺序，并且是非线程安全的。 ... [详细]

蜡笔小新 2024-11-18 16:58:22
copy
Java代码保护与混淆：ProGuard详解

在Java开发中，保护代码安全是一个重要的课题。由于Java字节码容易被反编译，因此使用代码混淆工具如ProGuard变得尤为重要。本文将详细介绍如何使用ProGuard进行代码混淆，以及其基本原理和常见问题。 ... [详细]

蜡笔小新 2024-11-18 16:46:17
get
使用Bash脚本将Medium文章迁移到个人博客[教程]

尽管Medium是一个优秀的发布平台，但在其之外拥有自己的博客仍然非常重要。这不仅提供了另一个与读者互动的渠道，还能确保您的内容安全。本文将介绍如何使用Bash脚本将Medium文章迁移到个人博客。 ... [详细]

蜡笔小新 2024-11-18 11:26:14
get
SCOI2012 奇怪的游戏：结论与网络流应用

本题涉及一些特殊情况，例如黑白块数不相等的情况，这些情况不满足二分性质。对于有解的情况，可以通过特定公式直接计算出结果。本文将详细介绍如何使用网络流来解决这类问题。 ... [详细]

蜡笔小新 2024-11-16 16:59:14

灰灰t2502911555

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章