Leetcode3165. 不包含相邻元素的子序列的最大和(Go中的线段树分治包含多类数据使用maintain进行维护)

题目截图

在这里插入图片描述

题目分析

不能取相邻的,就是打家劫舍
然后更改某一个值就是单点更新
更新后,需要更新区间的值
需要注意的是,使用分治时需要考虑到一头一尾的问题,所以有4种情况(选or不选在两个位置)
这四种情况需要在maintain中维护

ac code

// f00 表示第一个数一定不选,最后一个数一定不选
// f01 表示第一个数一定不选,最后一个数可选可不选
// f10 表示第一个数可选可不选,最后一个数一定不选
// f11 表示第一个数可选可不选,最后一个数可选可不选,也就是没有任何限制
// 答案是根节点的f11,没有任何限制
// 按照分治的思想结合线段树处理
// 线段树包含以上四个f进行maintain
type data struct {f00, f01, f10, f11 int}
type seg []data func(t seg) maintain(o int) {// 左右孩子a, b := t[o<<1], t[o<<1|1]t[o] = data {max(a.f00 + b.f10, a.f01 + b.f00),max(a.f00 + b.f11, a.f01 + b.f01),max(a.f10 + b.f10, a.f11 + b.f00),max(a.f10 + b.f11, a.f11 + b.f01),}
}func(t seg) build (a []int, o, l, r int) {if l == r {// 边界只需考虑f11,其他都不能取t[o].f11 = max(a[l], 0)return}m := (l + r) >> 1t.build(a, o<<1, l, m)t.build(a, o<<1|1, m + 1, r)t.maintain(o)
}// 单点更新
func(t seg) update(o, l, r, i, val int) {if l == r {// 边界只需考虑f11,其他都不能取t[o].f11 = max(val, 0)return}m := (l + r) >> 1if i <= m {t.update(o<<1, l, m, i, val)} else {t.update(o<<1|1, m + 1, r, i, val)}t.maintain(o)
}func maximumSumSubsequence(nums []int, queries [][]int) (ans int) {n := len(nums)t := make(seg, 2<<bits.Len(uint(n)))t.build(nums, 1, 0, n - 1)for _, q := range queries {t.update(1, 0, n - 1, q[0], q[1])ans += t[1].f11 // f11是整个数组的没有限制}return ans % 1_000_000_007
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/338190.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

利用 Scapy 库编写 Teardrop 攻击脚本

一、介绍 Teardrop攻击是一种历史上比较著名的拒绝服务&#xff08;Denial of Service, DoS&#xff09;攻击&#xff0c;主要利用了IP数据包分片和重组过程中的漏洞来攻击目标系统。以下是对Teardrop攻击的详细介绍&#xff1a; 1.1 攻击原理 IP协议允许数据包在传输过程中…

jpom ruoyi 发布后端

添加ssh 添加标签 添加仓库 添加构建 构建 命令 APP_NAMEenterprise IMAGE_NAMEenterprise:latest APP_PORT8080 RUN_ENVjenkins cd ruoyi-admin docker stop $APP_NAME || true docker rm $APP_NAME || true docker rmi $IMAGE_NAME || true docker build -f Dockerfil…

System-Verilog 实现DE2-115倒车雷达模拟

System-Verilog 实现DE2-115倒车雷达模拟 引言&#xff1a; 随着科技的不断进步&#xff0c;汽车安全技术也日益成为人们关注的焦点。在众多汽车安全辅助系统中&#xff0c;倒车雷达以其实用性和高效性脱颖而出&#xff0c;成为现代汽车不可或缺的一部分。倒车雷达系统利用超声…

Django ORM魔法:用Python代码召唤数据库之灵!

探索Django ORM的神奇世界&#xff0c;学习如何用Python代码代替复杂的SQL语句&#xff0c;召唤数据库之灵&#xff0c;让数据管理变得轻松又有趣。从基础概念到高级技巧&#xff0c;阿佑带你一步步成为Django ORM的魔法师&#xff0c;让你的应用开发速度飞起来&#xff01; 文…

【Java】面向对象的三大特征:封装、继承、多态

封装 什么叫封装&#xff1f; 在我们写代码的时候经常会涉及两种角色&#xff1a; 类的实现者 和 类的调用者。 封装的本质就是让类的调用者不必太多的了解类的实现者是如何实现类的&#xff0c; 只要知道如何使用类就行了&#xff0c;这样就降低了类使用者的学习和使用成本&a…

Windows环境安装redis

1、下载redis https://github.com/tporadowski/redis/releases 2、解压 .zip 3、更改文件名 更改文件名称为&#xff1a;redis 4、将本地解压后的redis&#xff0c;作为本地服务器下的应用服务 从redis文件路径下&#xff0c;执行cmd .\redis-server --service-install re…

LeetCode - 贪心(Greedy)算法集合(Python)[分配问题|区间问题]

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/139242199 贪心算法&#xff0c;是在每一步选择中&#xff0c;都采取当前状态下&#xff0c;最好或最优&#xff08;即最有利&#xff09;的选择&…

基于SSM框架的手机商城项目

后端: 订单管理 客户管理&#xff1a; 商品管理 类目管理 前端&#xff1a; 首页&#xff1a;

Python 学习笔记【1】

此笔记仅适用于有任一编程语言基础&#xff0c;且对面向对象有一定了解者观看 文章目录 数据类型字面量数字类型数据容器字符串列表元组 type()方法数据类型强转 注释单行注释多行注释 输出基本输出连续输出&#xff0c;中间用“,”分隔更复杂的输出格式 变量定义del方法 标识符…

基础—SQL—DQL(数据查询语言)排序查询

一、引言 排序查询这里面涉及的关键字&#xff1a;ORDER BY。在我们日常的开发中&#xff0c;这个是很常见的&#xff0c;比如打开一个网购的商城&#xff0c;这里面可以找到一个销量的排序、综合的排序、价格的排序&#xff08;升序、降序&#xff09;等等。接下来就学习这一部…

8-Django项目--登录及权限

目录 templates/login/login.html templates/login/404.html views/login.py utils/pwd_data.py auth.py settings.py 登录及权限 登录 views.py 中间件 auth.py templates/login/login.html {% load static %} <!DOCTYPE html> <html lang"en"&g…

19.1 简易抽奖

准备一个数组&#xff0c;里面添加10个奖品数据&#xff0c;让奖品数据快速的在盒子中随机显示&#xff0c;通过按钮控制盒子里面的内容停止。 效果图&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8">&…

高效派单的秘诀:探索运维工单处理软件的五大关键功能-亿发

在快节奏的现代企业运营中&#xff0c;如何高效管理生产流程&#xff0c;确保任务按时完成&#xff0c;同时保持产品质量和客户满意度&#xff0c;是每个管理者面临的重要课题。工单管理系统&#xff0c;作为企业数字化转型的关键工具&#xff0c;正逐渐成为解决这些问题的利器…

C++进阶篇章:set与map(pair , multiset , multimap)

目录 1.关联式容器与序列式容器 2.pair&#xff08;键值对&#xff09; 3.set 构造函数 find函数 count函数&#xff1a; insert函数 4.multiset 5.map insert函数 operator[] 1.关联式容器与序列式容器 C中关联式容器与序列式容器是两种不同的容器 1.关联式容器 关…

极验4点选逆向 JS逆向分析 最新版验证码

目录 声明&#xff01; 一、请求流程分析 二、加密参数w与payload 三、参数w生成位置 四、结果展示&#xff1a; 原创文章&#xff0c;请勿转载&#xff01; 本文内容仅限于安全研究&#xff0c;不公开具体源码。维护网络安全&#xff0c;人人有责。 声明&#xff01; 本文章…

丢失的数字 ---- 位运算

题目链接 题目: 分析: 解法一: 哈希表解法二: 高斯求和解法三:位运算 异或运算根据运算的性质, 相同的两个a异或 0 以示例一为例: 数组中有0,1,3, 缺失的数字是2, 那么只要我们将数组与0,1,2,3 异或, 就会得到2 代码: class Solution {public int missingNumber(int[] num…

JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短期记忆神经网络多特征分类预测

JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短期记忆神经网络多特征分类预测 目录 JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短期记忆神经网络多特征分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短…

图形学初识--屏幕空间变换

文章目录 前言正文为什么需要屏幕空间变换&#xff1f;什么是屏幕空间变换&#xff1f;屏幕空间变换矩阵如何推导&#xff1f;问题描述步骤描述 结尾&#xff1a;喜欢的小伙伴点点关注赞哦! 前言 前面章节主要讲解了视图变换和投影变换&#xff0c;此时距离在屏幕空间显示也就…

2024年6月1日 (周六) 叶子游戏新闻

Embracer探讨单机游戏大作涨价超过70美元的可能性在Embracer集团等待公布新公司名称的同时&#xff0c;他们对游戏大作的价格上涨做出了评论。几年来&#xff0c;游戏大作的价格已经达到了70美元的门槛。Embracer集团的CEO Lars Wingefors在采访中表示&#xff0c;电子游戏行业…

ch5链路层和局域网

回顾TCP/IP参考模型&#xff0c;明确链路层和物理层在整个模型中的地位&#xff0c;简要提出链路层要解决的问题是单段链路的数据传输&#xff0c;物理层解决的是数字信号与电气信号之间的相互转换。 链路层概述 节点&#xff1a;主机和路由器(包括网桥和交换机) 链路&#xf…