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

推荐阅读

const
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
const
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
const
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
const
火星商店问题：线段树分治与持久化Trie树的应用

本题涉及编号为1至n的火星商店，每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品，以及查询某段时间内某些商店中所有商品（含永久商品）与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]

蜡笔小新 2024-12-27 21:23:11
text
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
get
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12
const
MySQL索引详解与优化

本文深入探讨了MySQL中的索引机制，包括索引的基本概念、优势与劣势、分类及其实现原理，并详细介绍了索引的使用场景和优化技巧。通过具体示例，帮助读者更好地理解和应用索引以提升数据库性能。 ... [详细]

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

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

蜡笔小新 2024-12-24 10:44:24
get
深入理解KMP算法中的next数组：北大OJ 2406题解

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

蜡笔小新 2024-12-28 11:30:01
import
Java 中 Writer flush()方法，示例

Java 中 Writer flush()方法，示例 ... [详细]

蜡笔小新 2024-12-28 06:41:52
cmd
Dockerfile 编写与 Docker 网络配置详解

本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用，涵盖基础指令、镜像构建与发布流程，并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]

蜡笔小新 2024-12-27 17:31:41
cmd
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
cmd
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
cmd
Tetris 排名系统 (拓扑排序与并查集的应用)

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

蜡笔小新 2024-12-24 21:03:51
get
数据结构入门：栈的基本概念与操作

本文详细介绍了栈这一重要的数据结构，包括其基本概念、顺序存储结构、栈的基本操作（如入栈、出栈、清空栈和销毁栈），以及如何利用栈实现二进制到十进制的转换。通过具体代码示例，帮助读者更好地理解和应用栈的相关知识。 ... [详细]

蜡笔小新 2024-12-24 13:47:59

灰灰t2502911555

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

Tags | 热门标签

RankList | 热门文章