当前位置: 首页 > news >正文

LeeCode 3165 线段树

题意

传送门 LeeCode 3165 不包含相邻元素的子序列的最大和

题解

考虑不含相邻子序列的最大和,在不带修改的情况下容易想到,以最后一个元素是否被选取为状态进行DP。从线性递推的角度难以处理待修改的情况。

从分治的角度考虑,使用线段树维护区间内包含或不包含边界元素的信息,即可快速维护答案。总时间复杂度 O ( m log ⁡ n ) O(m\log n) O(mlogn)

#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
constexpr long long INF = 1e15;
struct SegmentTree {struct Node {array<long long, 4> a;Node() : a{-INF, -INF, -INF, -INF} {}Node operator+(Node& rhs) {Node res;auto _max = [](auto& x, auto y) {x = max(x, y);};for (int i = 0; i < 4; ++i) {for (int j = 0; j < 4; ++j) {if(a[i] == -INF || rhs.a[j] == -INF) {continue;}int i1 = i / 2, i2 = i % 2;int j1 = j / 2, j2 = j % 2;if (i2 == j1 && i2 == 1) {continue;}int k1 = i1, k2 = j2;_max(res.a[k1 * 2 + k2], a[i] + rhs.a[j]);}}return res;}long long get() {long long res = -INF;for (auto x : a) {res = max(res, x);}return res;}};vector<Node> dat;SegmentTree(vector<int>& a) {int n = a.size();int k = 1;while (k < n) {k *= 2;}k *= 2;dat.resize(k);function<void(int, int, int)> init = [&](int p, int l, int r) {if (r - l == 1) {dat[p].a = {0, -INF, -INF, a[l]};return;}int m = (l + r) / 2;int chl = p * 2 + 1, chr = p * 2 + 2;init(chl, l, m);init(chr, m, r);dat[p] = dat[chl] + dat[chr];};init(0, 0, n);}void update(int a, int b, int x, int p, int l, int r) {if (a <= l && r <= b) {dat[p].a = {0, -INF, -INF, x};return;}if (r <= a || b <= l) {return;}int m = (l + r) / 2;int chl = p * 2 + 1, chr = p * 2 + 2;update(a, b, x, chl, l, m);update(a, b, x, chr, m, r);dat[p] = dat[chl] + dat[chr];}
};class Solution {public:int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();SegmentTree tr(nums);int m = queries.size();long long res = 0;for (int i = 0; i < m; ++i) {int j = queries[i][0], x = queries[i][1];tr.update(j, j + 1, x, 0, 0, n);res += tr.dat[0].get();res %= MOD;}return (res + MOD) % MOD;}
};

相关文章:

LeeCode 3165 线段树

题意 传送门 LeeCode 3165 不包含相邻元素的子序列的最大和 题解 考虑不含相邻子序列的最大和&#xff0c;在不带修改的情况下容易想到&#xff0c;以最后一个元素是否被选取为状态进行DP。从线性递推的角度难以处理待修改的情况。 从分治的角度考虑&#xff0c;使用线段树…...

修改元组元素

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 场景模拟&#xff1a;伊米咖啡馆&#xff0c;由于麝香猫咖啡需求量较大&#xff0c;库存不足&#xff0c;店长想把它换成拿铁咖啡。 实例08 将麝香猫…...

【模版方法设计模式】

文章目录 模板方法设计模式模板方法的设计原则模板方法设计模式组成部分代码实现抽象类实现具体实现类执行 模板方法设计模式 模版方法设计模式&#xff08;Template Method Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了一个操作中的算法骨架&#xff0c;而将一…...

rust语言初识

程序设计实践课上水一篇ing 来源&#xff1a;rust基础入门-1.初识rust-酷程网 (kucoding.com) rust作为一名新兴语言&#xff0c;与go又有些许不同&#xff0c;因为它的目标是对标系统级开发&#xff0c;也就是C、C这两位在编程界的位置。比如我们最常用的windows系统&#x…...

知识图谱数据预处理笔记

知识图谱数据预处理笔记 0. 引言1. 笔记1-1. \的转义1-2. 特殊符号的清理1-3. 检查结尾是否正常1-4. 检查<>是否存在1-5. 两端空格的清理1-6. 检查object内容长时是否以<开始 0. 引言 最近学习知识图谱&#xff0c;发现数据有很多问题&#xff0c;这篇笔记记录遇到的…...

Unity面试八股文之基础篇

文章目录 前言1. Unity的生命周期加载第一个场景Editor在第一次帧更新之前帧之间更新顺序协程销毁对象时退出时 2. Unity 协程和线程,进程的区别3. 本地坐标系 世界坐标系4. 碰撞器和触发器的区别后话 前言 开设这个栏目的博文会写一些有关unity的面试题目&#xff0c;在面试的…...

HTTPS能否避免流量劫持?如何实现HTTPS

在当今数字化时代&#xff0c;网站安全已经成为企业和个人的头等大事。随着网络犯罪和数据泄露的增加&#xff0c;保护您的网站免受潜在威胁比以往任何时候都更加重要。网站安全的一个关键组成部分是HTTPS&#xff0c;它代表着安全的超文本传输协议。HTTPS是标准HTTP协议的安全…...

簡述Vue 2.0 响应式数据的原理

Vue 2.0 响应式数据的原理主要基于以下几个关键点&#xff1a; 数据劫持与Object.defineProperty&#xff1a; Vue 2.0 使用 Object.defineProperty 方法来劫持对象的属性&#xff0c;为其添加 getter 和 setter 方法。当数据被访问或修改时&#xff0c;这些 getter 和 setter …...

Kafka线上集群部署方案怎么做?no.6

专栏前面几期内容&#xff0c;我分别从Kafka的定位、版本的变迁以及功能的演进等几个方面循序渐进地梳理了Apache Kafka的发展脉络。通过这些内容&#xff0c;我希望你能清晰地了解Kafka是用来做什么的&#xff0c;以及在实际生产环境中该如何选择Kafka版本&#xff0c;更快地帮…...

vscode 的 AI 协助插件 Tabnine / Codeium

4.1、Tabnine 描述&#xff1a;Tabnine 是一款基于深度学习技术的代码自动补全工具。该插件支持多种编程语言&#xff0c;包括 Python、JavaScript、TypeScript、Java 和 Go 等。它可以根据您输入的代码段和上下文信息&#xff0c;预测并推荐可能的代码补全选项&#xff0c;从而…...

Flutter 中的 OutlineButton 小部件:全面指南

Flutter 中的 OutlineButton 小部件&#xff1a;全面指南 在Flutter的Material Design组件库中&#xff0c;OutlineButton是一个用于创建带边框的扁平按钮的小部件。这种按钮通常用于次要操作或在需要强调其他按钮的情况下使用。本文将为您提供一个全面的指南&#xff0c;帮助…...

Kubernetes可视化界面之DashBoard

1.1 DashBoard Kubernetes Dashboard 是 Kubernetes 集群的一个开箱即用的 Web UI&#xff0c;提供了一种图形化的方式来管理和监视 Kubernetes 集群中的资源。它允许用户直接在浏览器中执行许多常见的 Kubernetes 管理任务&#xff0c;如部署应用、监控应用状态、执行故障排查…...

Docker学习(4):部署web项目

一、部署vue项目 在home目录下创建项目目录 将打包好的vue项目放入该目录下&#xff0c;dist是打包好的vue项目 在项目目录下&#xff0c;编辑default.conf 内容如下&#xff1a; server {listen 80;server_name localhost; # 修改为docker服务宿主机的iplocation / {r…...

驱动开发中引入私有数据的原因

系列文章目录 驱动开发中引入私有数据的原因 驱动开发中引入私有数据的原因 系列文章目录驱动开发中引入私有数据的原因 驱动开发中引入私有数据的原因 驱动开发中引入私有数据&#xff08;Private Data&#xff09;概念主要是为了解决以下几个关键问题&#xff1a; 1.多设备支…...

删除edge浏览器文本框储存记录值以及关闭自动填充

当我们点击输入框时总会出现许多以前输入过的信息。 一、删除edge浏览器文本框储存记录值 1、首先按下↓键选中你想删除的信息 二、关闭自动填充。 1、在地址栏输入edge://wallet/settings跳转到以下界面 2、往下滑找到 全部取消即可...

mysql事务 事务并发问题 隔离级别 以及原理

mysql事务 简介&#xff1a;事务是一组操作的集合&#xff0c;它是一个不可分割的工作单位&#xff0c;事务会把所有的操作作为一个整体一起向系统提交或撤销操作请求&#xff0c;即这些操作要么同时成功&#xff0c;要么同时失败。 事务四大特性 原子性&#xff08;Atomici…...

Android 性能为王时代SparseArray和HashMap一争高下

文章目录 一、SparseArray 源码分析1. **类定义和构造函数**2. **基本方法**2.1 put(int key, E value)2.2 get(int key)2.3 delete(int key)2.4 removeAt(int index)2.5 gc()2.6 size()2.7 keyAt(int index) 和 valueAt(int index) 3. **辅助方法**3.1 binarySearch() 二、使用…...

学术图表的基本配色方法

不论是商业图表还是专业图表&#xff0c;图表的配色都极其关键。图表配色主要有彩色和黑白两种配色方案。刘万祥老师曾提出&#xff1a; “在我看来&#xff0c;普通图表与专业图表的差别&#xff0c;很大程度就体现在颜色运用上。” 对于科学图表&#xff0c;大部分国内的期…...

【学习笔记】Webpack5(Ⅱ)

Webpack 3、高级篇 3.1、提升开发体验 —— SourceMap 3.2、提升打包速度 3.2.1 HotModuleReplacement 3.2.2 OneOf 3.2.3 Include / Exclude 3.2.4 Cache 3.2.5 Thread 3.3、减少代码体积 …...

oracle碎片整理

1、move碎片整理 1) DECLARE tmp_val VARCHAR2 (500); BEGIN FOR REC IN (SELECT TABLE_NAME FROM USER_TABLES ) LOOP tmp_val:=ALTER TABLE || REC.TABLE_NAME || MOVE; BEGIN EXECUTE IMMEDIATE tmp_val; DBMS_OUTPUT.ENABLE(buffer_size => null); DBMS_OUTPUT.put_l…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...