算法笔记————ST表

运用了倍增思想,从小到大处理

1.【模板】ST 表

// Problem: 
//     P3865 【模板】ST 表
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3865
// Memory Limit: 125 MB
// Time Limit: 800 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int d[N][20];
#define endl '\n'

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>d[i][0];
    for(int i=1;i<=19;++i){
    	for(int j=1;j+(1<<i)-1<=n;++j){
    		d[j][i]=max(d[j][i-1],d[j+(1<<(i-1))][i-1]);
    	}
    }	
    while(m--){
    	int a,b;cin>>a>>b;
    	int len=log2(b-a+1);
    	cout<<max(d[a][len],d[b-(1<<len)+1][len])<<endl;
    }
    
    return 0;
}

董晓博客的图解释的比较详细,这里引用

第一个图是预处理,时间复杂度nlogn,第二个图是查询,复杂度是O(1)

遇上大数据的离线处理就只能用ST表

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Kotlin学习日志(一)TextView、Button、Toast的使用(1)

android:layout_width“wrap_content” android:layout_height“wrap_content”/> import kotlinx.android.synthetic.main.activity_main.* 这句话的意思是引进Kotlin的的控件变量自动映射功能&#xff0c;接下来只要是这个activity_main.xml文件中的控件&#xff0c;我…

非关系型数据库——Redis基本操作

目录 一、Redis数据库常用命令 1.Set——存放数据 2.Get——获取数据 3.Keys——获取符合条件的键值 4.Exists——判断键值是否存在 5.Del——删除指定键值 6.Type——获取键值对应的类型 7.Rename——对已有键值重命名&#xff08;覆盖&#xff09; 8.Renamenx——对…

160 Linux C++ 通讯架构实战14,epoll 反应堆模型

到这里&#xff0c;我们需要整理一下之前学习的epoll模型&#xff0c;并根据之前的epoll模型&#xff0c;提出弊端&#xff0c;进而整理epoll反应堆模型&#xff0c;进一步深刻理解&#xff0c;这是因为epoll实在是太重要了。 复习之前的epoll的整体流程以及思路。 参考之前写…

虚幻UE5智慧城市全流程开发教学

一、背景 这几年&#xff0c;智慧城市/智慧交通/智慧水利等飞速发展&#xff0c;骑士特意为大家做了一个这块的学习路线。 二、这是学习大纲 1.给虚幻UE5初学者准备的智慧城市/数字孪生蓝图开发教程 https://www.bilibili.com/video/BV1894y1u78G 2.UE5数字孪生蓝图开发教学…

【软件工程】测试规格

1. 引言 1.1简介 本次的测试用例是基于核心代码基本开发完毕&#xff0c;在第一代系统基本正常运行后编写的&#xff0c;主要目的是为了后续开发与维护的便利性。 该文档主要受众为该系统后续开发人员&#xff0c;并且在阅读此文档前最后先阅读本系统的需求文档、概要设计文…

海外视频网站推广实战需掌握的10个关键性数据指标-华媒舍

在海外视频网站推广实战中&#xff0c;了解和掌握一些关键性数据指标是非常重要的。这些指标可以帮助我们评估视频网站的推广效果&#xff0c;优化推广策略&#xff0c;提升用户体验。以下是推广人员在实战中应该了解和关注的十个关键性数据指标&#xff1a; 1. 视频创意点击率…

PS入门|规规矩矩的图形怎么抠出来?

前言 上一次讲解到用魔棒工具蒙版可以把需要的区域抠出来&#xff0c;但仅适用于边缘锐利的类型。 但魔棒工具并不适用于边缘区域有过渡色的内容&#xff0c;比如下面这张照片&#xff1a; 如果直接使用魔棒工具进行选择&#xff0c;就会出现下面这种情况&#xff1a; 在边界…

数据挖掘入门项目二手交易车价格预测之建模调参

文章目录 目标步骤1. 调整数据类型&#xff0c;减少数据在内存中占用的空间2. 使用线性回归来简单建模3. 五折交叉验证4. 模拟真实业务情况5. 绘制学习率曲线与验证曲线6. 嵌入式特征选择6. 非线性模型7. 模型调参&#xff08;1&#xff09; 贪心调参&#xff08;2&#xff09;…

内表GROUP BY

内表GROUP BY REPORT z_test_table_lhy. DATA: price TYPE sflight-price. SELECT MIN( price ) AS m,carridINTO DATA(t_temp)FROM sflightGROUP BY carridHAVING MAX( price ) > 10. "Having从句中比较统计结果时&#xff0c;需要将统计函数重写一遍&#xff0c;而不…

Android数据存储技术

一、文件存储 <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"android:orientation"vertical"android:layout_width"match_parent"android:layout_height"match_parent" ><EditTextandroid:id&qu…

树莓派安装Windows搭建网盘和下载机

0 需求分析 在同一个局域网内&#xff0c;同时有多种设备&#xff08;Windows&#xff0c;Linux&#xff0c;Android&#xff09;需要进行大量的数据共享。另外&#xff0c;还时常需要从百度网盘/夸克网盘等网盘下载文件。不难看出&#xff0c;我的需求很简单&#xff0c;就是…

异常的处理

异常处理概述 在编写程序时&#xff0c;经常要在可能出现错误的地方加上检测的代码&#xff0c;如进行x/y运算时&#xff0c;要检测分母为0&#xff0c;数据为空&#xff0c;输入的不是数据而是字符等。过多的if-else分支会导致程序的代码加长、臃肿&#xff0c;可读性差&…

论文笔记:Large Language Models as Analogical Reasoners

iclr 2024 reviewer打分5558 1 intro 基于CoT prompt的大模型能够更好地解决复杂推理问题 然而传统CoT需要提供相关的例子作为指导&#xff0c;这就增加了人工标注的成本——>Zero-shot CoT避免了人工标注来引导推理 但是对于一些复杂的任务难以完成推理&#xff0c;例如c…

Ubuntu22.04中基于Qt开发Android App

文章目录 前言在Ubuntu22.04中配置开发环境案例测试参考 前言 使用Qt开发手机应用程序是一种高效且灵活的选择。Qt作为一个跨平台的开发框架&#xff0c;为开发者提供了统一的开发体验和丰富的功能库。首先&#xff0c;Qt的跨平台性让开发者可以使用相同的代码库在不同的操作系…

SSM项目实战——哈哈音乐(四)前台模块开发

1、项目准备 ①导入依赖和前端资源 <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.x…

路由策略与路由控制之双点双向重发布(OSPF-ISIS)实验

双点双向重发布在路由协议中&#xff0c;特别是在OSPF&#xff08;开放式最短路径优先&#xff09;与IS-IS&#xff08;中间系统到中间系统&#xff09;等协议之间&#xff0c;指的是在两个协议间或者两个进程间进行路由信息共享的机制。这种机制涉及到在两个不同的协议区域使用…

微软推出GPT-4 Turbo优先使用权:Copilot for Microsoft 365商业用户享受无限制对话及增强图像生成能力

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

电脑上音频太多,播放速度又不一致,如何批量调节音频播放速度?

批量调节音频速度是现代音频处理中的一个重要环节&#xff0c;尤其在音乐制作、电影剪辑、有声书制作等领域&#xff0c;它能够帮助制作者快速高效地调整音频的播放速度&#xff0c;从而满足特定的制作需求。本文将详细介绍批量调节音频速度的方法、技巧和注意事项&#xff0c;…

Docker 安装 Linux 系统可视化监控 Netdata

docker 安装 netdata 前提准备Docker 两种方式部署 Netdata1、使用 docker run 命令运行 netdata 服务2、使用 docker compose 运行 netdata 服务 Netdata 服务可视化界面Netdata 汉化处理 前提准备 说明&#xff1a;此处使用 windows11 安装的 docker desktop & wsl2/apli…

【Rust】环境搭建

Rust 支持很多的集成开发环境&#xff08;IDE&#xff09;或开发专用的文本编辑器。 官方网站公布支持的工具如下&#xff08;工具 - Rust 程序设计语言&#xff09; 本课程将使用 Visual Studio Code 作为我们的开发环境&#xff08;Eclipse 有专用于 Rust 开发的版本&#…