算法提高之你能回答这些问题吗
算法提高之你能回答这些问题吗
-
核心思想:线段树
- 用sum,lmax,rmax,tmax分别存线段长度,最大前缀,最大后缀,最大子段和
-
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 500010;int n,m;int w[N];struct Node{int l,r;int sum,lmax,rmax,tmax;}tr[N*4];void pushup(Node &u,Node &l,Node &r){u.sum = l.sum + r.sum;u.lmax = max(l.lmax,l.sum + r.lmax);u.rmax = max(r.rmax,r.sum + l.rmax);u.tmax = max(max(l.tmax,r.tmax) , l.rmax + r.lmax);}void pushup(int u){pushup(tr[u],tr[u<<1],tr[u<<1|1]);}void build(int u,int l,int r){if(l == r) tr[u] = {l,r,w[r],w[r],w[r],w[r]};else{tr[u] = {l,r};int mid = l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}}void modify(int u,int x,int v){if(tr[u].l == x && tr[u].r == x) tr[u] = {x,x,v,v,v,v};else{int mid = tr[u].l+tr[u].r>>1;if(x <= mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);pushup(u);}}Node query(int u,int l,int r){if(tr[u].l >= l && tr[u].r <= r) return tr[u];else{int mid = tr[u].l + tr[u].r >>1;if(r <= mid) return query(u<<1,l,r);else if(l >mid) return query(u<<1|1,l,r);else{auto left = query(u<<1,l,r);auto right = query(u<<1|1,l,r);Node res;pushup(res,left,right);return res;}}}int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>w[i];build(1,1,n);int k,x,y;while (m -- ){cin>>k>>x>>y;if(k==1){if(x>y) swap(x,y);cout<<query(1,x,y).tmax<<endl;}else modify(1,x,y);}}
相关文章:
算法提高之你能回答这些问题吗
算法提高之你能回答这些问题吗 核心思想:线段树 用sum,lmax,rmax,tmax分别存线段长度,最大前缀,最大后缀,最大子段和 #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N 500010;int n,m;int w[N];s…...
C++-指针
在C中,指针是至关重要的组成部分。它是C语言最强大的功能之一,也是最棘手的功能之一。 指针具有强大的能力,其本质是协助程序员完成内存的直接操纵。 指针:特定类型数据在内存中的存储地址,即内存地址。 指针变量的定…...
Three.js 研究:2、如何让动画线性运动
1、默认的动画含有加速度并非线性的 制作好的动画很明显是非线性的,这是一个运动环,为了让环运行线性进行如下设置。 2、设置动画成为线性动画...
z3-加法器实验
补码器加减法,运算方法简介 我们要知道什么是补码的加法,我们为什么要用补码的加法? 补码的加法其实就是将两个补码形式的二进制数字直接相加,处理的时候忽略超出固定位数的进位。补码的加法运算和无符号二进制数的加法操作一样&…...
解决git克隆项目出现fatal无法访问git clone https://github.com/lvgl/lvgl.git
Windows 11系统 报错 $ git clone https://github.com/lvgl/lvgl.git Cloning into lvgl... fatal: unable to access https://github.com/lvgl/lvgl.git/: Failed to connect to github.com port 443 after 21141 ms: Couldnt connect to server 解决方法 git运行这两段代码…...
Vue中引入组件需要哪三步
在Vue中引入组件通常需要以下三步: 导入组件:首先,你需要在父组件中导入你想要使用的子组件。这通常是通过ES6的import语法完成的。 注册组件:接下来,你需要在父组件中注册这个子组件。这可以通过components选项完成&…...
到底该用英文括号还是中文括号?
这篇博客写的还挺详细的,不错。...
一个普通双非女生的秋招之路
大家好,我是小布丁。 先简单地做个自我介绍: 我今年本科毕业于某双非院校(属于那种没什么人听说过的小学校),学的是计算机专业,英语四级水平(没办法,六级确实没过)。我本…...
一个模型用了几层神经网络怎么算?
有权重参数的层算作一层,没有权重参数的就是参数不更新,不能称之为一层 有权重:卷积层、全连接层 没有权重的层:激活函数层、池化层 即数卷积层和全连接层的个数,就是这个模型用了几层神经网络。...
python获取cookie的方式
通过js获取cookie,避免反复登录操作。 经验证在JD上没有用,cookie应该无痕或者加密了,只能用单浏览器不关的模式来实现,但是代码留着,其他网站可能有用。 def cookie_set():driver webdriver.Chrome(optionschrome_…...
Nginx-狂神说
Nginx概述 公司产品出现瓶颈? 我们公司项目刚刚上线的时候,并发量小,用户使用的少,所以在低并发的情况下,一个jar包启动应用就够了,然后内部tomcat返回内容给用户。 但是慢慢的,使用我们平台…...
Python筑基之旅-运算符
目录 一、运算符 1、了解定义 2、理解意义 2-1、基本数据处理 2-2、条件判断 2-3、逻辑操作 2-4、赋值和更新 2-5、位操作 2-6、提高代码可读性 2-7、解决实际问题 2-8、学习其他编程语言的基础 3、探索方法 3-1、理解概念 3-2、练习基本运算 3-3、掌握优先级 …...
【Text2SQL】Spider 数据集
论文:Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task ⭐⭐⭐⭐⭐ EMNLP 2018, arXiv:1809.08887 Dataset: spider GitHub: github.com/taoyds/spider 一、论文速读 本文提出了 Text2SQL 方向的…...
语雀——云知识库/笔记
对于日常进行学习/创作或是记录学习、工作内容与心得的群体来说,能够及时同步的云笔记应用有着广泛的应用场景。近期,我也探索了许多款不同的软件应用,今天来分享一款很有特点的应用——语雀。 语雀,为每一个人提供优秀的文档和知…...
Java学习:电影查询简单系统
1.创建一个movice的对象来存放电影 里面设置构造器(有参和无参) package com.movie;public class movice {//创建一个movice的对象存放电影private int id;private String name;private double price;private double score;private String diector;pri…...
在Mac电脑下怎么部署QAnything?
在Mac电脑下部署QAnything,可以选择使用纯Python环境进行部署,这种方式不依赖GPU,适合在Mac等笔记本电脑上运行。以下是基于QAnything的纯Python环境安装教程的步骤[18]: 安装要求 Python 3.10(建议使用Anaconda3来管…...
单条16g和双条8g哪个好
单条16g和双条8g各有优劣,具体选择要根据个人需求和电脑配置来决定。 以下是一些参考信息: •单条16g内存的价格比双条8g内存的价格低,而且16g的内存容量大,一条内存十分的方便。 •两条8g内存可以组成双通道,电脑运行速度要快一些。 •对于普通使用电脑的人群与热衷于…...
Microsoft VBA Excel 去重小工具
问题简述 在本工作表中,A1:B3单元格样式如下,通过名称管理器B列的单元格被命名为"LinkFile"、“SheetName”、“InputArea”,请实现以下功能:读取Excel文件中的数据,去除重复的数据,并记录每个数…...
数据库管理-第194期 网络加速RDMA初探(20240526)
数据库管理194期 2024-05-26 数据库管理-第194期 网络加速RDMA初探(20240526)1 概念2 发展3 使用总结 数据库管理-第194期 网络加速RDMA初探(20240526) 作者:胖头鱼的鱼缸(尹海文) Oracle ACE A…...
C++小游戏 合集
生化危机 #include<conio.h> #include<string.h> #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<time.h> #include<direct.h> int n,round,gold0; bool f1,f2,f3,deadfalse,PC_64Bit; char str[4]; struct n…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
