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

推荐阅读

get
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
get
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
get
使用动态规划算法求解0-1背包问题

本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现，详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]

蜡笔小新 2024-12-27 19:17:15
get
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
text
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
import
Transforming the Future of Virtual Worlds

Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]

蜡笔小新 2024-12-28 09:44:49
get
Handling Null Object Encoding in OAuth 1.0a API Implementation

Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]

蜡笔小新 2024-12-28 08:54:34
text
技术分享：从动态网站提取站点密钥的解决方案

本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]

蜡笔小新 2024-12-28 04:11:47
import
Java 中的 BigDecimal pow()方法，示例

Java 中的 BigDecimal pow()方法，示例 ... [详细]

蜡笔小新 2024-12-27 20:54:03
get
新浪笔试题

1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]

蜡笔小新 2024-12-27 19:32:17
get
词根词缀解析：greg、hap、helio及其他词源故事

本文基于刘洪波老师的《英文词根词缀精讲》，深入探讨了多个重要词根词缀的起源及其相关词汇，帮助读者更好地理解和记忆英语单词。 ... [详细]

蜡笔小新 2024-12-27 18:59:50
import
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新 2024-12-27 18:51:49
text
使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表

本文介绍了一段通用代码示例，该代码不仅能够操作 Azure Active Directory (AAD)，还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级：AAD 和 Subscription。 ... [详细]

蜡笔小新 2024-12-27 16:07:12
spring
深入解析Spring Cloud Ribbon负载均衡机制

本文详细介绍了Spring Cloud中的Ribbon组件如何实现服务调用的负载均衡。通过分析其工作原理、源码结构及配置方式，帮助读者理解Ribbon在分布式系统中的重要作用。 ... [详细]

蜡笔小新 2024-12-27 16:01:25
spring
Docker的安全基准

nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]

蜡笔小新 2024-12-28 13:00:24

灰灰t2502911555

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

Tags | 热门标签

RankList | 热门文章