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

推荐阅读

include
紫荆花之恋：动态树上的小精灵友谊问题

本题来自WC2014，题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系，要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]

蜡笔小新 2024-12-22 14:36:54
include
2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

本次考试于2016年10月25日上午7:50至11:15举行，主要涉及数学专题，特别是斐波那契数列的性质及其在编程中的应用。本文将详细解析考试中的题目，并提供解题思路和代码实现。 ... [详细]

蜡笔小新 2024-12-25 13:08:21
header
深入理解Redis的数据结构与对象系统

本文详细探讨了Redis中的数据结构和对象系统的实现，包括字符串、列表、集合、哈希表和有序集合等五种核心对象类型，以及它们所使用的底层数据结构。通过分析源码和相关文献，帮助读者更好地理解Redis的设计原理。 ... [详细]

蜡笔小新 2024-12-25 04:11:22
include
图论问题解析：POJ2762 从u到v或从v到u的可达性判断（强连通分量缩点与单向连通性检测）

本文深入探讨了POJ2762问题，旨在通过强连通分量缩点和单向连通性的判断方法，解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤，并附带完整的代码示例。 ... [详细]

蜡笔小新 2024-12-24 10:44:24
include
如何高效清空C++标准输入缓冲区

本文探讨了在C++中如何有效地清空输入缓冲区，确保程序只处理最近的输入并丢弃多余的输入。我们将介绍一种不阻塞的方法，并提供一个具体的实现方案。 ... [详细]

蜡笔小新 2024-12-23 15:44:01
sum
树链问题的优化解法：深度优先搜索与质因数分解

本文介绍了一种通过深度优先搜索（DFS）和质因数分解来解决最长树链问题的方法。我们通过枚举树链上的最大公约数（GCD），将所有节点按其质因子分类，并计算每个类别的最长链，最终求得全局最长链。 ... [详细]

蜡笔小新 2024-12-23 11:59:34
include
JSOI2010 蔬菜庆典：树结构中的无限大权值问题

本文探讨了 JSOI2010 的蔬菜庆典问题，主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性，提出了有效的解决方案，并详细解释了算法的实现过程。 ... [详细]

蜡笔小新 2024-12-22 18:57:48
io
VC++如何监控cpu fan 转速?

主板IO用W83627THG,用VC如何取得CPU温度,系统温度,CPU风扇转速,VBat的电压. ... [详细]

蜡笔小新 2024-12-22 13:48:42
io
优化Windows系统以提升DAW性能

配置Windows操作系统以确保DAW（数字音频工作站）硬件和软件的高效运行可能是一个复杂且令人沮丧的过程。本文提供了一系列专业建议，帮助你优化Windows系统，确保录音和音频处理的流畅性。 ... [详细]

蜡笔小新 2024-12-25 09:41:14
include
Tetris 排名系统 (拓扑排序与并查集的应用)

本题旨在通过给定的评级信息，利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表，或者是否存在冲突或信息不足的情况。 ... [详细]

蜡笔小新 2024-12-24 21:03:51
window
实现页面自动加载更多内容功能：类微博和Pinterest的设计

在现代Web应用中，当用户滚动到页面底部时，自动加载更多内容的功能变得越来越普遍。这种无刷新加载技术不仅提升了用户体验，还优化了页面性能。本文将探讨如何实现这一功能，并介绍一些实际应用案例。 ... [详细]

蜡笔小新 2024-12-23 17:01:04
include
C++ 中的链表实现与应用

本文介绍如何在 C++ 中使用链表结构存储和管理数据。通过具体示例，展示了静态链表的基本操作，包括节点的创建、链接及遍历。 ... [详细]

蜡笔小新 2024-12-23 14:22:40
export
JavaScript 基础语法指南

本文详细介绍了 JavaScript 的基础语法，包括变量、数据类型、运算符、语句和函数等内容，旨在为初学者提供全面的入门指导。 ... [详细]

蜡笔小新 2024-12-23 10:54:44
header
Python处理Word文档的高效技巧

本文详细介绍了如何使用Python处理Word文档，涵盖从基础操作到高级功能的各种技巧。我们将探讨如何生成文档、定义样式、提取表格数据以及处理超链接和图片等内容。 ... [详细]

蜡笔小新 2024-12-23 10:40:32
require
使用Fetch进行HTTP请求的基本示例

本文介绍了如何使用JavaScript的Fetch API与Express服务器进行交互，涵盖了GET、POST、PUT和DELETE请求的实现，并展示了如何处理JSON响应。 ... [详细]

蜡笔小新 2024-12-22 12:55:37

灰灰t2502911555

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

Tags | 热门标签

RankList | 热门文章