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

推荐阅读

hash
每日精选Codeforces训练题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）

题目涉及三种不同类型的算法问题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）。其中，1119E的问题背景是有n种不同长度的棍子，长度分别为2^0, 2^1, …, 2^(n-1)，每种棍子的数量为a[i]。任务是计算可以组成的三角形数量。根据三角形的性质，任意两边之和必须大于第三边。该问题可以通过贪心算法高效解决，通过合理选择棍子组合来最大化三角形的数量。 ... [详细]

蜡笔小新 2024-11-03 11:42:58
tree
如何高效启动大数据应用之旅？

在前一篇文章中，我探讨了大数据的定义及其与数据挖掘的区别。本文将重点介绍如何高效启动大数据应用项目，涵盖关键步骤和最佳实践，帮助读者快速踏上大数据之旅。 ... [详细]

蜡笔小新 2024-11-04 18:30:38
tree
深度优先搜索解题报告：NOJ1102 黑白图像问题分析与实现

针对NOJ1102黑白图像问题，本文采用深度优先搜索算法进行详细分析与实现。该问题要求在给定的时间限制（普通Java为1000-3000毫秒）和内存限制（65536KByte）内，处理一个n×n的黑白图像。通过对图像的逐像素遍历，利用深度优先搜索算法有效地识别并标记相连的黑色区域，从而实现图像的高效处理。实验结果显示，该方法在多种测试用例中均能稳定达到预期效果，具有较高的准确性和效率。 ... [详细]

蜡笔小新 2024-11-04 16:22:16
hash
基址获取与驱动开发：内核中提取ntoskrnl模块的基地址方法解析

基址获取与驱动开发：内核中提取ntoskrnl模块的基地址方法解析 ... [详细]

蜡笔小新 2024-11-04 15:56:02
tree
HDU 1166 敌军布阵：利用线段树计算区间和

在HDU 1166敌军布阵问题中，通过运用线段树数据结构，可以高效地计算指定区间的敌军数量。该算法不仅能够在限定的时间和内存条件下快速求解，还能够灵活应对动态变化的战场局势，为实时决策提供支持。 ... [详细]

蜡笔小新 2024-11-03 17:55:45
go
51Nod 1640：晴朗天气下的神奇魔法现象分析

在晴朗天气条件下，对一种神奇的魔法现象进行了深入分析。该题目为原创，基准时间限制为1秒，空间限制为131072KB，分值20，属于3级难度的算法题。研究发现，这种魔法现象在阳光明媚的环境中表现得尤为显著，进一步探讨了其背后的科学原理和技术实现方法。 ... [详细]

蜡笔小新 2024-11-03 15:21:50
require
如何在 Node.js 环境中将 CSV 数据转换为标准的 JSON 文件格式？

如何在 Node.js 环境中将 CSV 数据转换为标准的 JSON 文件格式？ ... [详细]

蜡笔小新 2024-11-02 17:32:17
object
深入解析OpenCV中的人脸检测算法实现

本文详细探讨了OpenCV中人脸检测算法的实现原理与代码结构。通过分析核心函数和关键步骤，揭示了OpenCV如何高效地进行人脸检测。文章不仅提供了代码示例，还深入解释了算法背后的数学模型和优化技巧，为开发者提供了全面的理解和实用的参考。 ... [详细]

蜡笔小新 2024-11-02 13:37:20
php
HDU 2176 石子游戏：多堆Nim博弈策略分析

在多堆石子游戏中，通过分析Nim博弈策略，探讨了如何在限定时间和内存条件下实现最优解。本文详细研究了石子游戏中的数学原理和算法优化方法，旨在为参与者提供有效的策略指导。具体而言，文章讨论了不同堆数下的Nim值计算及其应用，帮助玩家在复杂的博弈环境中取得优势。 ... [详细]

蜡笔小新 2024-11-02 10:46:31
hash
【并发编程】全面解析 Java 内存模型，一篇文章带你彻底掌握

本文深入解析了 Java 内存模型（JMM），从基础概念到高级特性进行全面讲解，帮助读者彻底掌握 JMM 的核心原理和应用技巧。通过详细分析内存可见性、原子性和有序性等问题，结合实际代码示例，使开发者能够更好地理解和优化多线程并发程序。 ... [详细]

蜡笔小新 2024-11-02 09:09:51
hash
Linux 信号处理全面解析（第六篇）

本文深入探讨了信号及其来源。信号本质上是对中断机制的软件层面模拟，从原理上看，进程接收到信号与处理器接收到中断请求类似。信号具有异步特性，能够在进程执行过程中随时触发，从而中断当前操作并执行相应的处理程序。文章详细分析了信号的生成、传递和处理机制，并讨论了常见的信号类型及其应用场景。此外，还介绍了如何在 Linux 系统中使用信号进行进程间通信和错误处理，为开发者提供了实用的技术指导。 ... [详细]

蜡笔小新 2024-11-01 18:25:29
go
Prim算法优化实现：基于优先队列的最小生成树构建方法

Prim算法在处理稠密图时表现出色，尤其适用于边数远多于顶点数的情形。传统实现的时间复杂度为 \(O(n^2)\)，但通过引入优先队列进行优化，可以在点数为 \(m\)、边数为 \(n\) 的情况下显著降低时间复杂度，提高算法效率。这种优化方法不仅能够加速最小生成树的构建过程，还能在大规模数据集上保持良好的性能表现。 ... [详细]

蜡笔小新 2024-11-01 16:06:14
go
如何在TypeScript中定义可选为空的类型？ - Declaring Types as Optionally Nullable in TypeScript

在TypeScript中，我定义了一个名为 `Employee` 的接口，其中包含 `id` 和 `name` 属性。为了使这些属性可选为空，可以通过使用 `| null` 或 `| undefined` 来扩展其类型定义。例如，`id: number | null` 表示 `id` 可以是数字或空值。这种类型的灵活性在处理不确定的数据时非常有用，可以提高代码的健壮性和可维护性。 ... [详细]

蜡笔小新 2024-11-05 10:19:41
go
寻找最长无重复字符的子字符串

寻找最长无重复字符的子字符串 ... [详细]

蜡笔小新 2024-11-05 00:05:58
go
在 Windows 10 环境下配置 VSCode 进行 Linux C++ 开发时的智能代码提示（基于 WSL）

在 Windows 10 环境中，通过配置 Visual Studio Code (VSCode) 实现基于 Windows Subsystem for Linux (WSL) 的 C++ 开发，并启用智能代码提示功能。具体步骤包括安装 VSCode 及其相关插件，如 CCIntelliSense、TabNine 和 BracketPairColorizer，确保在 WSL 中顺利进行开发工作。此外，还详细介绍了如何在 Windows 10 中启用和配置 WSL，以实现无缝的跨平台开发体验。 ... [详细]

蜡笔小新 2024-11-03 18:43:38

灰灰t2502911555

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

Tags | 热门标签

RankList | 热门文章