ST表(区间查询

解决的问题:

  • 数组区间查询最大值和最小值
  • 对于解决数组的树状数组的区间修改 ------- 线段树
  • 倍增思想

在这里插入图片描述
在这里插入图片描述

核心代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int num[N];
int f[N][N];
int main(){int n;cin>>n;//输入默认从1开始 for(int i=1;i<=n;i++) cin>>num[i];//创建st表for(int i=0;i<=20;i++){//枚举区间长度 2*i次方//2的20次方大约1.04e6 //当区间太大  会一直continue for(int j=1;j+(1<<i)-1<=n;j++){//区间末尾:j+2的i次方-1 不能越界 f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);//j到j+1<<i-1区间 由两个一半的区间组成//所以时间复杂度为nlogn }} //查询函数//给定左右闭区间l,R 查询最大值 int l,r;cin>>l>>r;int qujian=log2(r-l+1);//查看区间长度对应的log图//通过先分裂区间后 利用区间交集的方式去查询//记得左右  会用到lr  右边不能从l入手  从r入手 int res=max(f[l][qujian],f[r-(1<<qujian)+1][qujian]);cout<<res<<endl;return 0; }

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

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

相关文章

Vue 2.x时间转换为北京时间(+8)

文章目录 当前时间格式效果图理想时间格式效果图转换方法总结 当前时间格式效果图 非中国常用时间格式&#xff0c;在上图中给可以看到&#xff0c;选择的时间为&#xff1a;2024-8-26 ~ 2024-8-27&#xff0c;返回结果却是&#xff1a;2024-08-25TXX:XX:XXZ&#xff0c;明显不…

最大噪音值甚至受法规限制,如何基于LBM算法有效控制风扇气动噪音

风扇的气动噪声 在工业设备行业&#xff0c;最大噪音值受法规限制。在很多使用风扇冷却的设备上&#xff0c;风扇噪声通常是这些设备工作噪声的最大贡献量。而在家电民用行业&#xff0c;例如空调、空气净化器、油烟机等&#xff0c;其噪音大小直接关系到用户的体验感受&#x…

实现并发网络服务器

一&#xff0c;网络服务器 1.单循环网络服务器 —— 同一时刻只能处理一个客户端任务 2.并发服务器 —— 同一时刻能处理多个客户端任务 二&#xff0c;并发服务器 1.多线程 2.IO多路复用 3.多进程 三&#xff0c;IO模型 1.阻塞IO 阻塞IO&#xff08;Blocking IO&…

SQLi-LABS通关攻略【41-45】

SQLi-LABS 41关 这一关是堆叠注入 测试闭合 ?id1 //回显错误 ?id1-- //回显错误 ?id1-- //回显正确 所以是数字型的注入 测试堆叠注入&#xff0c;更改Dumb的密码 ?id1;update users set password123456 where usernameDumb-- SQLi-…

不会PS怎么快速抠图?试试这3种方法,抠图干净又高效!

我就不信每个人都会用PS抠图&#xff01;&#xff01; 关于抠图技巧&#xff0c;前面高赞已经分享了好多&#xff0c;但&#xff0c;我还是忍不住想向所有小白推荐更“傻瓜式”抠图。 就是那种根本不需要学习就能抠干净的抠图工具&#xff0c;适用于99%的抠图需求&#xff0c…

【数字时序】时钟树延迟偏差——CPPR adjustment

接上一篇文章Innovus的时序报告解读&#xff0c;新版的貌似多了一些信息&#xff0c;比如CPPR Adjustment和Derate。不太清楚这两个是什么概念&#xff0c;搜索之后转载2篇后端工程师的博客如下&#xff1a; 搜到个这个网站好像有很多后端相关的知识点分享一哈&#xff1a; Co…

springboot+vue+mybatis计算机毕业设计电子产品交易系统+PPT+论文+讲解+售后

系统根据现有的管理模块进行开发和扩展&#xff0c;采用面向对象的开发的思想和结构化的开发方法对电子产品交易管理的现状进行系统调查。采用结构化的分析设计&#xff0c;该方法要求结合一定的图表&#xff0c;在模块化的基础上进行系统的开发工作。在设计中采用“自下而上”…

书店销售内部后台管理系统员工信息部门图书入库账目集成分析销售客户

本系统的设计实施为书店管理系统的运行做基础&#xff0c;为书店的管理提供良好的条件。系统主要实现了&#xff1a;员工信息管理、部门管理、图书管理、入库管理、账目集成分析、销售管理、客户管理。 2.1系统开发工具 本系统主要使用JSP技术对系统进行设计和开发。JSP拥有Jav…

上书房信息咨询:医疗满意度调研

随着人们生活水平的不断提高&#xff0c;医疗服务的需求日益增长。近期&#xff0c;上书房信息咨询受托完成了某市医疗市场的满意度调研&#xff0c;旨在深入了解市民对医疗服务的评价和需求&#xff0c;为提升医疗服务质量提供有力支持。 近年来&#xff0c;某市致力于推进医…

本地生活本地推软件有哪些?手把手教你从零开始提升转化率!

当前&#xff0c;多家互联网大厂在本地生活版块的布局不断深入&#xff0c;让本地生活市场不断焕发新活力的同时&#xff0c;也使得竞争态势日益激烈。在此背景下&#xff0c;对于本地生活服务商而言&#xff0c;无论是想要拓展品牌商家资源&#xff0c;还是想要改善交付效果&a…

Java毕业设计 基于SpringBoot vue药店管理系统

Java毕业设计 基于SpringBoot vue药店管理系统 SpringBoot 药店管理系统 功能介绍 管理员 登录 修改个人资料 密码修改 门店管理 销售业绩 药品管理 进货管理 库存管理 会员管理 员工管理 店长 登录 修改个人资料 密码修改 销售业绩 药品管理 进货管理 库存管…

【设计模式-策略】

定义 策略模式是一种行为型设计模式&#xff0c;它定义了一系列算法&#xff0c;并将每个算法封装起来&#xff0c;使它们可以互相替换&#xff0c;且算法的变化不会影响到使用算法的客户。通过使用策略模式&#xff0c;算法可以在运行时根据需要动态地进行更换&#xff0c;从…

Golang | Leetcode Golang题解之第372题超级次方

题目&#xff1a; 题解&#xff1a; const mod 1337func pow(x, n int) int {res : 1for ; n > 0; n / 2 {if n&1 > 0 {res res * x % mod}x x * x % mod}return res }func superPow(a int, b []int) int {ans : 1for _, e : range b {ans pow(ans, 10) * pow(a…

前端页面调用本地exe,打开exe主界面

一、文件配置 在桌面新建文件Start.txt 复制以下内容&#xff0c;保存后修改后缀名.txt为 .reg。 Windows Registry Editor Version 5.00 [HKEY_CLASSES_ROOT\Start] "URL Protocol""D:\\Task\\app.exe" "Start Protocol" [HKEY_CLASSES_ROOT\…

第20讲 动画讲解轻松学会STM32的PWM

来源&#xff1a;【STM32】动画讲解轻松学会STM32的PWM_哔哩哔哩_bilibili 基本概念 周期/频率 计算公式&#xff1a;PWM周期1个高电平用时1个低电平用时 PWM的频率1/周期 如图所示此时周期为1ms&#xff0c;即1s内存在1000组这样的高低电平&#xff0c;PWM的频率为1000hz。…

Python自动化办公2.0 课程更新

之前的课程&#xff0c;包含了Python pandassklearn 数据分析&#xff0c;和Stremlit 可视化仪表盘的开发 和一系列自动化项目案例的开发&#xff0c;包括我们封装了ztl-uia 模块&#xff0c;可以同时自动化操控windows 软件和浏览器, 封装的模块&#xff0c;针对为付费学员使…

使用 FinalShell 链接 Centos

1. 安装 FinalShell 下载地址&#xff1a;https://www.hostbuf.com/t/988.html 2. 查看 IP地址。 2.1 通过命令查询IP 输入 ip addr show 查询&#xff0c;输出效果如下截图&#xff0c;其中的 192.168.1.5 就是 IP 地址。 2.2 通过可视化界面查询IP 点击右上角的网络图标…

亲测分享:这个获客工具,精准又好用!

如何高效、精准地获取目标客户成为了每一家企业都面临的重大挑战。传统的获客方式不仅效率低下&#xff0c;而且成本高昂&#xff0c;往往难以达到预期的营销效果。 今天&#xff0c;我就作为一位亲身体验者&#xff0c;向大家分享这个精准又好用的获客工具——易拓客。 随时…

论文辅助笔记:Large Language Models are Zero-Shot Next LocationPredictors

论文理论部分&#xff1a;论文笔记&#xff1a;lunLarge Language Models are Zero-Shot Next LocationPredictors-CSDN博客 2 Data 2.1 Dataset类 2.2 下载文件 2.3 get_dataset 2.4 get_trajectories trajectory_split暂时略去 # save the test dictionary and the true l…

cad导出为jpg图片的方法,分享这三种方法

在工程设计、建筑设计或任何需要使用CAD&#xff08;计算机辅助设计&#xff09;软件的领域&#xff0c;将CAD图纸转换成JPG图片格式是日常工作中不可或缺的一环。无论是为了更便捷地在网络上分享设计稿&#xff0c;还是为了在非CAD环境中展示设计成果&#xff0c;掌握CAD到JPG…