题解:SP1741 TETRIS3D - Tetris 3D
这是一道二维线段树(树套树)+标记永久化的模版题
前置知识点(来自董晓算法)
好,现在开始我们的分析:
题意简述:
在一个二维平面内,有给定的坐标,在这个坐标范围内加上这个物品的厚度。最后输出不超过极限的最高坐标。
解法分析:
由于看到了区间修改,所以第一时间想到了线段树。(好像树状数组也可以做,只是本人不会)但是,要注意到这是一个二维线区间修改,所以要引入一种新的东西:二维线段树(什么!你还没有点开前置知识点?!快去看看!)
因为有董晓老师对于二维线段树的详细讲解了,我在这里就不过多赘述。
发现问题:
对于内层而言,传统的做法可以胜任,可以打 lazy 标记,pushdown 和 pushup 也都是可以进行的。但是对于外层而言,信息量太大,无法进行,所以需要使用一种新办法:标记永久化。
知识点,标记永久化
好了,问题到这就已经解决了,直接上代码吧。(四十几行真的不长了QAQ)
#include<iostream>
#include<cstring>
#include<algorithm>
#define ls(x) x*2
#define rs(x) x*2+1
#define mid l+(r-l)/2
using namespace std;
const int MAXN=4e3+10;
int d,s,n;
int a,b,h,x,y;
struct segy{int mx[MAXN],tag[MAXN];void change(int u,int l,int r,int y1,int y2,int h){mx[u]=max(mx[u],h);if(y1<=l&&r<=y2){tag[u]=max(tag[u],h);return ;}if(y1<=mid)change(ls(u),l,mid,y1,y2,h);if(y2>mid)change(rs(u),mid+1,r,y1,y2,h);}int query(int u,int l,int r,int y1,int y2){if(y1<=l&&r<=y2)return mx[u];int ans=tag[u];if(y1<=mid)ans=max(ans,query(ls(u),l,mid,y1,y2));if(y2>mid)ans=max(ans,query(rs(u),mid+1,r,y1,y2));return ans;}
}mx[MAXN],tag[MAXN];
void change(int u,int l,int r,int x1,int x2,int y1,int y2,int h){mx[u].change(1,1,s,y1,y2,h);if(x1<=l&&r<=x2){tag[u].change(1,1,s,y1,y2,h);return ;}if(x1<=mid)change(ls(u),l,mid,x1,x2,y1,y2,h);if(x2>mid)change(rs(u),mid+1,r,x1,x2,y1,y2,h);
}
int query(int u,int l,int r,int x1,int x2,int y1,int y2){if(x1<=l&&r<=x2)return mx[u].query(1,1,s,y1,y2);int ans=tag[u].query(1,1,s,y1,y2);if(x1<=mid)ans=max(ans,query(ls(u),l,mid,x1,x2,y1,y2));if(x2>mid)ans=max(ans,query(rs(u),mid+1,r,x1,x2,y1,y2));return ans;
}
int main(){cin>>d>>s>>n;for(int i=1;i<=n;i++){cin>>a>>b>>h>>x>>y;x++;y++;h+=query(1,1,d,x,x+a-1,y,y+b-1);change(1,1,d,x,x+a-1,y,y+b-1,h);}cout<<mx[1].mx[1]<<"\n";return 0;
}
相关文章:
题解:SP1741 TETRIS3D - Tetris 3D
这是一道二维线段树(树套树)标记永久化的模版题 前置知识点(来自董晓算法) 好,现在开始我们的分析: 题意简述: 在一个二维平面内,有给定的坐标,在这个坐标范围内加上…...
EWSTM8 IAR for STM8 软件分享
1. 软件简介 EWSTM8,即 IAR for STM8,全称为 IAR Embedded Workbench for STM8,它是 IAR ARM 嵌入式工作台之一,用于开发 STM8。IAR 有多个不同名的版本,对应不同的开发对象。 EWSTM8最新版本为V3.11(202…...
非机动车检测数据集 4类 5500张 电动三轮自行车 voc yolo
非机动车检测数据集 4类 5500张 电动三轮自行车 voc yolo 非机动车检测数据集介绍 数据集名称 非机动车检测数据集 (Non-Motorized Vehicle Detection Dataset) 数据集概述 该数据集专为训练和评估基于YOLO系列目标检测模型(包括YOLOv5、YOLOv6、YOLOv7等&#x…...
Chromium 中JavaScript FileReader API接口c++代码实现
FileReader 备注: 此特性在 Web Worker 中可用。 FileReader 接口允许 Web 应用程序异步读取存储在用户计算机上的文件(或原始数据缓冲区)的内容,使用 File 或 Blob 对象指定要读取的文件或数据。 文件对象可以从用户使用 <…...
k8s 中微服务之 MetailLB 搭配 ingress-nginx 实现七层负载
目录 1 MetailLB 搭建 1.1 MetalLB 的作用和原理 1.2 MetalLB功能 1.3 部署 MetalLB 1.3.1 创建deployment控制器和创建一个服务 1.3.2 下载MealLB清单文件 1.3.3 使用 docker 对镜像进行拉取 1.3.4 将镜像上传至私人仓库 1.3.5 将官方仓库地址修改为本地私人地址 1.3.6 运行清…...
南昌网站建设让你的企业网站更具竞争力
南昌网站建设让你的企业网站更具竞争力 在当今竞争激烈的市场环境中,一个高质量的网站不仅是企业形象的展示平台,更是吸引客户、提升业绩的重要工具。南昌作为江西的省会城市,互联网产业的蓬勃发展为企业网站建设提供了良好的机遇。 首先&am…...
【重学 MySQL】五十三、MySQL数据类型概述和字符集设置
【重学 MySQL】五十三、MySQL数据类型概述和字符集设置 MySQL数据类型概述MySQL字符集设置注意事项 MySQL数据类型概述 MySQL是一个流行的关系型数据库管理系统,它支持多种数据类型,以满足不同数据处理和存储的需求。理解并正确使用这些数据类型对于提高…...
《计算机原理与系统结构》学习系列——计算机的算数运算(上)
系列文章目录 目录 ALU行波进位加法器超前进位加法器整数运算加减法乘法无符号数相乘N位乘法数的工作流程N位乘法器改进:硬件资源更快速的乘法 MIPS中的乘法除法 32位除法器流程除法器改进 更快速的除法 MIPS中的除法总结 ALU ALU功能:对a,…...
如何在华为云服务器查看IP地址,及修改服务器登录密码!!!
1.在华为云服务器查看IP地址 (1).第一步: 先找到控制台 (2).第二步: 点击华为云Flexus云服务 (3)第三步: 找到公网IP,就找到华为云服务器IP地址啦。 注意:在操作以上步骤的前提是要已注册华为云账号及购买云服务器…...
JAVA并发编程高级——JDK 新增的原子操作类 LongAdder
LongAdder 简单介绍 前面讲过,AtomicLong通过CAS提供了非阻塞的原子性操作,相比使用阻塞算法的同步器来说它的性能已经很好了,但是JDK开发组并不满足于此。使用AtomicLong 时,在高并发下大量线程会同时去竞争更新同一个原子变量,但是由于同时只有一个线程的CAS操作会成功,…...
常见的基础系统
权限管理系统支付系统搜索系统报表系统API网关系统待定。。。 Java 优质开源系统设计项目 来源:Java 优质开源系统设计项目 | JavaGuide 备注:github和gitee上可以搜索到相关项目...
在 window 系统下安装 Ubuntu (虚拟机)
文章目录 零、Ubuntu 和 Vmware workstation 资源一、下载 Ubuntu二、下载 Vmware Workstation Pro三、安装 Vmware Workstation Pro四、创建虚拟机五、配置 Ubuntu 零、Ubuntu 和 Vmware workstation 资源 如果觉得自己下载 Ubuntu 和 Vmware workstation 麻烦,也…...
鸿蒙开发(NEXT/API 12)【访问控制应用权限管控概述】程序访问控制
默认情况下,应用只能访问有限的系统资源。但某些情况下,应用存在扩展功能的诉求,需要访问额外的系统数据(包括用户个人数据)和功能,系统也必须以明确的方式对外提供接口来共享其数据或功能。 系统通过访问…...
(10)MATLAB莱斯(Rician)衰落信道仿真1
文章目录 前言一、莱斯分布随机变量二、仿真代码与结果1.仿真代码2.仿真结果画图 后续 前言 首先给出莱斯衰落信道模型,引入了莱斯因子K,并给出莱斯分布的概率密度函数公式。然后导出莱斯分布随机变量的仿真表示式,建立MATLAB仿真代码&#…...
什么是重卡充电桩?
有什么广告?没有广告,纯纯的介绍。 在政策与市场双重驱动下,充电桩市场已经开启加速模式,行业的火苗越烧越旺。同时,随着新能源重卡的广泛普及,重卡充电桩也迎来了新的发展机遇。 此种背景下 ,…...
模拟实现消息队列(基于SpringBoot实现)
提要:此处的消息队列是仿照RabbitMQ实现(参数之类的),实现一些基本的操作:创建/销毁交互机(exchangeDeclare,exchangeDelete),队列(queueDeclare,…...
C语言:预编译过程的剖析
目录 一.预定义符号和#define定义常量 二.#define定义宏 三.宏和函数的对比 四、#和##运算符 五、条件编译 在之前,我们已经介绍了.c文件在运行的过程图解,大的方面要经过两个方面。 一、翻译环境 1.预处理(预编译) 2.编译 3…...
算法——单调栈
单调栈: 保持栈内的元素始终递增或递减。 单调递增 待处理数组{1,5,2,5,7,2,8} public void sameyIncrease(int[] nums) {Stack<Integer> stack new Stack<>();for(int i 0; i < nums.length; i) {//当栈空的时候可以直接进栈或者要进栈的数大于…...
LeetCode讲解篇之695. 岛屿的最大面积
文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 我们遍历二维矩阵,如果当前格子的元素为1进行深度优先搜索,将搜索过的格子置为0,防止重复访问,然后对继续深度优先搜索上下左右中为1的格子 题解代码 func maxAr…...
招联2025校招内推倒计时
【投递方式】 直接扫下方二维码,或点击内推官网https://wecruit.hotjob.cn/SU61025e262f9d247b98e0a2c2/mc/position/campus,使用内推码 igcefb 投递) 【招聘岗位】 后台开发 前端开发 数据开发 数据运营 算法开发 技术运维 软件测试 产品策…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践
在电商行业蓬勃发展的当下,多平台运营已成为众多商家的必然选择。然而,不同电商平台在商品数据接口方面存在差异,导致商家在跨平台运营时面临诸多挑战,如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...
GraphRAG优化新思路-开源的ROGRAG框架
目前的如微软开源的GraphRAG的工作流程都较为复杂,难以孤立地评估各个组件的贡献,传统的检索方法在处理复杂推理任务时可能不够有效,特别是在需要理解实体间关系或多跳知识的情况下。先说结论,看完后感觉这个框架性能上不会比Grap…...
vxe-table vue 表格复选框多选数据,实现快捷键 Shift 批量选择功能
vxe-table vue 表格复选框多选数据,实现快捷键 Shift 批量选择功能 查看官网:https://vxetable.cn 效果 代码 通过 checkbox-config.isShift 启用批量选中,启用后按住快捷键和鼠标批量选取 <template><div><vxe-grid v-bind"gri…...
中国政务数据安全建设细化及市场需求分析
(基于新《政务数据共享条例》及相关法规) 一、引言 近年来,中国政府高度重视数字政府建设和数据要素市场化配置改革。《政务数据共享条例》(以下简称“《共享条例》”)的发布,与《中华人民共和国数据安全法》(以下简称“《数据安全法》”)、《中华人民共和国个人信息…...
