线段树保姆级教程
买水果
Description
水果姐今天心情不错,来到了水果街。
水果街有n家水果店,呈直线结构,编号为1~n,每家店能买水果也能卖水果,并且同一家店卖与买的价格一样。
学过oi的水果姐迅速发现了一个赚钱的方法:在某家水果店买一个水果,再到另外一家店卖出去,赚差价。
就在水果姐窃喜的时候,cgh突然出现,他为了为难水果姐,给出m个问题,每个问题要求水果姐从第x家店出发到第y家店,途中只能选一家店买一个水果,然后选一家店(可以是同一家店,但不能往回走)卖出去,求每个问题中最多可以赚多少钱。
Input
第一行n,表示有n家店
下来n个正整数,表示每家店一个苹果的价格。
下来一个整数m,表示下来有m个询问。
下来有m行,每行两个整数x和y,表示从第x家店出发到第y家店。
Output
有m行。
每行对应一个询问,一个整数,表示面对cgh的每次询问,水果姐最多可以赚到多少钱。
挺简单。
首先要维护一个最大mx和最小mn
然后维护一个_aa_和_bb_,分别表示从l~r或r~l的最大。
每次只需要去查询_aa_和_bb_(不需要修改)
pushup如下:
void pushup(int u) {tr[u].mx = max(tr[u << 1].mx,tr[u << 1 | 1].mx);tr[u].mn = min(tr[u << 1].mn,tr[u << 1 | 1].mn);tr[u]._aa_ = max({tr[u << 1 | 1].mx - tr[u << 1].mn,tr[u << 1]._aa_,tr[u << 1 | 1]._aa_});tr[u]._bb_ = max({tr[u << 1].mx - tr[u << 1 | 1].mn,tr[u << 1]._bb_,tr[u << 1 | 1]._bb_});
}
好做完了
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int w[N];
struct owl {int l, r,mx,mn,_aa_,_bb_;
} tr[N * 4];
void pushup(int u) {tr[u].mx = max(tr[u << 1].mx,tr[u << 1 | 1].mx);tr[u].mn = min(tr[u << 1].mn,tr[u << 1 | 1].mn);tr[u]._aa_ = max({tr[u << 1 | 1].mx - tr[u << 1].mn,tr[u << 1]._aa_,tr[u << 1 | 1]._aa_});tr[u]._bb_ = max({tr[u << 1].mx - tr[u << 1 | 1].mn,tr[u << 1]._bb_,tr[u << 1 | 1]._bb_});
}
void build(int u, int l, int r) {tr[u].l = l;tr[u].r = r;if (l == r) {tr[u].mx = tr[u].mn = w[l];return ;}int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}
int querymn(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) {return tr[u].mn;} else {int mid = tr[u].l + tr[u].r >> 1;int v = 2e9;if (l <= mid) {v = min(v, querymn(u << 1, l, r));}if (r > mid) {v = min(v, querymn(u << 1 | 1, l, r));}return v;}
}
int querymx(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) {return tr[u].mx;} else {int mid = tr[u].l + tr[u].r >> 1;int v = -2e9;if (l <= mid) {v = max(v, querymx(u << 1, l, r));}if (r > mid) {v = max(v, querymx(u << 1 | 1, l, r));}return v;}
}
int query_aa_(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) {return tr[u]._aa_;} else {int mid = tr[u].l + tr[u].r >> 1;int v = -2e9;if (l <= mid && mid < r){v = max(v,querymx(u << 1 | 1,mid + 1,r) - querymn(u << 1,l,mid));}if (l <= mid) {v = max(v, query_aa_(u << 1, l, r));}if (r > mid) {v = max(v, query_aa_(u << 1 | 1, l, r));}return v;}
}
int query_bb_(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) {return tr[u]._bb_;} else {int mid = tr[u].l + tr[u].r >> 1;int v = -2e9;if (l <= mid && mid < r){v = max(v,querymx(u << 1,l,mid) - querymn(u << 1 | 1,mid + 1,r));}if (l <= mid) {v = max(v, query_bb_(u << 1, l, r));}if (r > mid) {v = max(v, query_bb_(u << 1 | 1, l, r));}return v;}
}
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n, m;cin >> n;for (int i = 1; i <= n; i ++ ) {cin >> w[i];}cin >> m;build(1, 1, n);while (m -- ) {int l,r;cin >> l >> r;if (l < r){cout << query_aa_(1,l,r) << endl;}else{cout << query_bb_(1,r,l) << endl;}}return 0;
}
相关文章:
线段树保姆级教程
买水果 Description 水果姐今天心情不错,来到了水果街。 水果街有n家水果店,呈直线结构,编号为1~n,每家店能买水果也能卖水果,并且同一家店卖与买的价格一样。 学过oi的水果姐迅速发现了一个赚钱的方法:…...
logback之自定义过滤器
logback有两种过滤器,一种是context中的过滤器叫TurboFilter,是一个全局的过滤器,会影响所有的日志记录。另一种是Appender中的过滤器,只对所在的append有效。两者大同小异,这里我们以Appender的过滤器为例。 &#x…...
如何用CSS3创建圆角矩形并居中显示?
在网页设计中,圆角矩形因其美观和现代感而被广泛使用,居中显示元素也是一个常见的需求。今天,我们将学习如何使用CSS3的border-radius属性来创建圆角矩形,并将其居中显示在页面上。 如果你正在学习CSS,那么这个实例将非…...
Java 开发中的指定外部 Jar 路径详解
哈喽,各位小伙伴们,你们好呀,我是喵手。运营社区:C站/掘金/腾讯云/阿里云/华为云/51CTO;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互…...
python爬虫--小白篇【selenium自动爬取文件】
一、问题描述 在学习或工作中需要爬取文件资源时,由于文件数量太多,手动单个下载文件效率低,操作麻烦,采用selenium框架自动爬取文件数据是不二选择。如需要爬取下面网站中包含的全部pdf文件,并将其转为Markdown格式。…...
TI毫米波雷达原始数据解析之Lane数据交换
TI毫米波雷达原始数据解析之Lane数据交换 背景Lane 定义Lane 确认确认LVDS Lane 数量的Matlab 代码数据格式参考 背景 解析使用mmWave Studio 抓取的ADC Data Lane 定义 芯片与DCA100之间的数据使用LVDS接口传输,使用mmWave Studio 配置过程中有一个选项是LVDS L…...
overscroll-behavior-解决H5在ios上过度滚动的默认行为
1. 问题 开发H5的过程中,经常会有android和ios两边系统需要兼容的情况。在ios上一直有个问题是当H5内容触及到页面顶部或底部时,还是可以被人为的往下或往下拉动界面。当然可能有的情况是比较适用的,比如你往下拉动,然后在导航栏…...
Nacos配置中心总结
Nacos配置中心总结 Nacos配置文件的加载顺序和优先级 加载顺序 nacos作为配置中心时,需要在bootstrap.yml文件中添加nacos config相关的配置,这样系统启动时就能先去拉取nacos server上的配置了。拉取过来后会和本地配置文件进行合并。 bootstrap.ym…...
rouyi(前后端分离版本)配置
从gitee上下载,复制下载地址,到 点击Clone,下载完成, 先运行后端,在运行前端 运行后端: 1.配置数据库,在Navicat软件中,连接->mysql->名字自己起(rouyi-vue-blog),用户名roo…...
超大规模分类(一):噪声对比估计(Noise Contrastive Estimation, NCE)
NCE损失对应的论文为《A fast and simple algorithm for training neural probabilistic language models》,发表于2012年的ICML会议。 背景 在2012年,语言模型一般采用n-gram的方法,统计单词/上下文间的共现关系,比神经概率语言…...
Windows 下安装 triton 教程
目录 背景解决方法方法一:(治标不治本)方法二:(triton-windows)- 安装 MSVC 和 Windows SDK- vcredist 安装- whl 安装- 验证 背景 triton 目前官方只有Linux 版本,若未安装,则会出…...
复盘与导出工具最新版9.15重磅发布-全新UI兼容所有windows系统
在9.11版本的基础上大更新: 1.应付费用户需求修复当更换明亮风格时软件超过电脑屏幕的bug!!!!! 2.支持所有windows版本,32/64位的win xp/7/8/10/11 3.修复开盘啦涨停原因排序bug 4.全新ui风格 5提前爆料:.9.2版本的分开…...
家用电器销售系统|Java|SSM|JSP|
【技术栈】 1⃣️:架构: B/S、MVC 2⃣️:系统环境:Windowsh/Mac 3⃣️:开发环境:IDEA、JDK1.8、Maven、Mysql5.7 4⃣️:技术栈:Java、Mysql、SSM、Mybatis-Plus、JSP、jquery,html 5⃣️数据库可…...
NRF24L01模块通信实验
NRF24L01简要介绍 这里主要介绍模块的最重要的参数,废话就不多介绍了。 该模块是一款无线通信模块,一个模块即可同时具备发射和接收数据的功能,但是要想实现通信必须使用两个模块之间才能进行通信。NRF24L01模块使用的总线控制方式为SPI总…...
2024年12月CCF-GESP编程能力等级认证Scratch图形化编程三级真题解析
本文收录于《Scratch等级认证CCF-GESP图形化真题解析》专栏,专栏总目录:点这里,订阅后可阅读专栏内所有文章。 一、单选题(一共 15 个题目,每题 2 分,共 30 分) 第 1 题 2024 年 10 月 8 日,诺贝尔物理学奖“意外地”颁给了两位计算机科学家约翰霍普菲尔德(John J. …...
【MySQL系列】VARCHAR为啥一般是255
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
图文教程:使用PowerDesigner导出数据库表结构为Word/Html文档
1、第一种情况-无数据库表,但有数据模型 1.1 使用PowerDesigner已完成数据建模 您已经使用PowerDesigner完成数据库建模,如下图: 1.2 Report配置和导出 1、点击:Report->Reports,如下图: 2、点击&…...
Coroutine 基础五 —— Flow 之 Channel 篇
1、Channel 与 Flow 简介与对比 所有知识都可总结为一个字 —— 流。包括数据流、事件流、状态流。 开发中最常用的 StateFlow 提供状态订阅。可以将一些信息包进 StateFlow 中进行保存。比如界面上显示的字符串,或者系统级别的信息,如用户状态。装进 …...
快速掌握Elasticsearch检索之二:滚动查询(scrool)获取全量数据(golang)
Elasticsearch8.17.0在mac上的安装 Kibana8.17.0在mac上的安装 Elasticsearch检索方案之一:使用fromsize实现分页 1、滚动查询的使用场景 滚动查询区别于上一篇文章介绍的使用from、size分页检索,最大的特点是,它能够检索超过10000条外的…...
C++设计模式:状态模式(自动售货机)
什么是状态模式? 状态模式是一种行为型设计模式,它允许一个对象在其内部状态发生改变时,动态改变其行为。通过将状态相关的逻辑封装到独立的类中,状态模式能够将状态管理与行为解耦,从而让系统更加灵活和可维护。 通…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
