【高级数据结构】线段树
目录
最大数(单点修改,区间查询)
线段树1(区间修改,区间查询)
最大数(单点修改,区间查询)
洛谷:最大数https://www.luogu.com.cn/problem/P1198
题目描述
现在请求你维护一个数列,要求提供以下两种操作:
1、 查询操作。
语法:Q L
功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。
限制:L不超过当前数列的长度。(L>0)
2、 插入操作。
语法:A n
功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。
限制:n是整数(可能为负数)并且在长整范围内。
注意:初始时数列是空的,没有一个数。
输入格式
第一行两个整数,M 和 D,其中 M 表示操作的个数,D 如上文中所述。
接下来的 M 行,每行一个字符串,描述一个具体的操作。语法如上文所述。
输出格式
对于每一个查询操作,你应该按照顺序依次输出结果,每个结果占一行。
输入输出样例
输入 #1复制
5 100 A 96 Q 1 A 97 Q 1 Q 2
输出 #1复制
96 93 96
// Problem: T - 最大数
// Contest: Virtual Judge - 2023暑期训练-基本算法
// URL: https://vjudge.net/contest/568123#problem/T
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 2e5+5;struct node{int minv;
}seg[4*N];void update(int id){seg[id].minv=max(seg[id*2].minv,seg[id*2+1].minv);
}void build(int id,int l,int r){if(l==r){return;}int mid=(l+r)/2;build(id*2,l,mid);build(id*2+1,mid+1,r);update(id);
}void change(int id,int l,int r,int pos,int val){if(l==r){seg[id].minv=val;}else{int mid=(l+r)/2;if(pos<=mid) change(id*2,l,mid,pos,val);else change(id*2+1,mid+1,r,pos,val);update(id);}
}ll query(int id,int l,int r,int ql,int qr){if(l==ql&&r==qr){return seg[id].minv;}int mid=(l+r)/2;if(qr<=mid){return query(id*2,l,mid,ql,qr);}else if(ql>mid){return query(id*2+1,mid+1,r,ql,qr);}else{return max(query(id*2,l,mid,ql,mid),query(id*2+1,mid+1,r,mid+1,qr));}
}int main(){int n;ll p;cin>>n>>p;//build(1,1,n);int cnt=0,cur=0;for(int i=0;i<n;i++){char o;int x;cin>>o>>x;if(o=='A'){x=(x+cur)%p;change(1,1,n,cnt+1,x);cnt++;}else{cur=query(1,1,n,cnt-x+1,cnt);cout<<cur<<"\n";}}return 0; }
线段树1(区间修改,区间查询)
洛谷:线段树1https://www.luogu.com.cn/problem/P3372
题目描述
如题,已知一个数列,你需要进行下面两种操作:
- 将某区间每一个数加上 k。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 n,m,分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数,其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 33 或 44 个整数,表示一个操作,具体如下:
1 x y k
:将区间 [x,y] 内每个数加上 k。2 x y
:输出区间 [x,y] 内每个数的和。
输出格式
输出包含若干行整数,即为所有操作 2 的结果。
输入输出样例
输入 #1复制
5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4
输出 #1复制
11 8 20
相关文章:

【高级数据结构】线段树
目录 最大数(单点修改,区间查询) 线段树1(区间修改,区间查询) 最大数(单点修改,区间查询) 洛谷:最大数https://www.luogu.com.cn/problem/P1198 题目描述 …...

qt简易闹钟
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);ui->stopBtn->setDisabled(true);this->setFixedSize(this->size()); //设置固定大小this->s…...

python和c加加有什么区别,c和c++和python先学哪个
本篇文章给大家谈谈c加加编程和python编程有什么区别,以及python和c加加有什么区别,希望对各位有所帮助,不要忘了收藏本站喔。 1、python和c学哪个好 学C好。 C通常比Python更快,因为C是一种编译型语言,而Python则是…...

Visual Studio 2022 cmake配置opencv开发环境
1. 环境与说明 这里我用的是 widnows 10 64位,Visual Studio 用的 Visual Studio Community 2022 (社区版) 对于Android开发工程师来说,为什么要使用Visual Studio 呢 ? 因为在Visual Studio中开发调试OpenCV方便,可以开发调试好后…...

C++ GDAL找出多时相遥感影像缺失的日期并自动生成新的全零图像作为替补
本文介绍基于C 语言的GDAL库,基于一个存储大量遥感影像的文件夹,依据每一景遥感影像的文件名中表示日期的那个字段,找出这些遥感影像中缺失的成像日期,并新生成多个像元值全部为0的栅格文件,作为这些缺失日期当日的遥感…...

【AI底层逻辑】——篇章5(下):机器学习算法之聚类降维时间序列
续上: 目录 4、聚类 5、降维 6、时间序列 三、无完美算法 往期精彩: 4、聚类 聚类即把相似的东西归在一起,与分类不同的是,聚类要处理的是没有标签的数据集,它根据样本数据的分布特性自动进行归类。 人在认知是…...
P1980 [NOIP2013 普及组] 计数问题
[NOIP2013 普及组] 计数问题 题目描述 试计算在区间 1 1 1 到 n n n 的所有整数中,数字 x x x( 0 ≤ x ≤ 9 0\le x\le9 0≤x≤9)共出现了多少次?例如,在 1 1 1 到 11 11 11 中,即在 1 , 2 , 3 , 4…...

需求管理全过程流程图及各阶段核心关注点详解
分析报告指出,多达76%的项目失败是因为差劲的需求管理,这个是项目失败的最主要原因,比落后的技术、进度失控或者混乱的变更管理还要关键。很多项目往往在开始的时候已经决定了失败,谜底就在谜面上,开始就注定的失败&am…...
Android开源 自定义emoji键盘,EmojiPack v2.1版本
目录 一,简介 二、安装 添加jitpack 仓库 添加依赖: 混淆规则: 三、使用 1、一次性配置emoji显示处理 二、emoji的自定义键盘的使用 一,简介 EmojiPack当前已提供emoji的显示和emoji的选择自定义键盘,在emoji显示这一方面࿰…...
SOLIDWORKS软件的优势分析 硕迪科技
在现代的机械设计领域,SOLIDWORKS是一款备受青睐三维设计软件,它具备强大的建模和设计功能,在全球范围内广泛应用于机械设计和工程领域,为用户提供了全面的工程解决方案。本文就SOLIDWORKS的优势进行详细分析。 1、易于学习和使用…...

Android性能优化之游戏的Theme背景图
近期,对游戏的内存优化,通过内存快照发现,某个Activity的theme背景图 占用3M 多。考虑着手对齐进行优化。 问题 查看游戏中的内存快照,发现有一个图片bitmap 占用3M 多,设置在Activity的背景中: 查看Phon…...

网络安全(黑客)系统自学,成为一名白帽黑客
前言 黑客技能是一项非常复杂和专业的技能,需要广泛的计算机知识和网络安全知识。你可以参考下面一些学习步骤,系统自学网络安全。 在学习之前,要给自己定一个目标或者思考一下要达到一个什么样的水平,是学完找工作(…...
lua学习-2 常见运算符
文章目录 赋值运算符普通赋值多重赋值交换赋值 算数运算符常见符号标识 关系运算符常见符号标识TIP 逻辑运算符常见符号标识模拟三目运算 赋值运算符 普通赋值 a 1b "123"c truec "true"多重赋值 a,b 1,2 a,b,c 2,"ss" -- c的值为nil交换赋…...

【图像处理】使用 OpenCV 将您的照片变成卡通
图像到卡通 一、说明 在当今世界,我们被图像和视频所包围。从社交媒体到广告,图像已成为一种强大的交流媒介。但是你有没有想过,如果你能把你的照片变成卡通会发生什么?想象一下,为您最喜欢的照片创建动画版本…...

暖手宝UL认证 亚马逊UL测试报告 UL499测试项目
UL499测试内容:1、 漏电流测试 2、 输入测试 3、 潮态下漏电流测试4、正常温升测试 5、 耐高压测试 6、 稳定性测试7、异常测试(DRY)8、 异常测试 9、 静压及强度测试10、 烧熔断器测试、 电源线拉力测试11、 电源线推力测试12、 塑件变…...
ES6模块化与异步编程高级用法
1. ES6模块化 1.1 回顾:node.js 中如何实现模块化 node.js 遵循了 CommonJS 的模块化规范。其中: 导入其它模块使用 require() 方法模块对外共享成员使用 module.exports 对象 模块化的好处: 大家都遵守同样的模块化规范写代码࿰…...
spring-cloud-starter-gateway 4.0.6负载均衡失败
spring:application:name: gatewaycloud:gateway:routes:- id: memberuri: lb://memberpredicates:- Path/member/**需要引入下面负载均衡依赖否则503找不到服务 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-s…...
Tomcat注册为Windows服务
要将Tomcat注册为Windows服务,可以使用Tomcat提供的实用工具service.bat。以下是注册和配置Tomcat作为Windows服务的步骤: 打开命令提示符(Command Prompt)或 PowerShell,然后进入Tomcat安装目录的"bin"文件…...
【Maven】Maven 中 pom.xml 文件
文章目录 前言什么是 pom?pom配置一览 1. dependencies2.scope3.properties4.plugin参考 前言 Maven 是一个项目管理工具,可以对 Java 项目进行构建和管理依赖。 本文,我们认识下 pom.xml 文件。POM(Project Object Model, 项目…...
2、Linux驱动开发:模块_引用符号
目录 🍅点击这里查看所有博文 随着自己工作的进行,接触到的技术栈也越来越多。给我一个很直观的感受就是,某一项技术/经验在刚开始接触的时候都记得很清楚。往往过了几个月都会忘记的差不多了,只有经常会用到的东西才有可能真正记…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
C++ 类基础:封装、继承、多态与多线程模板实现
前言 C 是一门强大的面向对象编程语言,而类(Class)作为其核心特性之一,是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性,包括封装、继承和多态,同时讨论类中的权限控制,并展示如何使用类…...
Go 并发编程基础:select 多路复用
select 是 Go 并发编程中非常强大的语法结构,它允许程序同时等待多个通道操作的完成,从而实现多路复用机制,是协程调度、超时控制、通道竞争等场景的核心工具。 一、什么是 select select 类似于 switch 语句,但它用于监听多个通…...
NLP常用工具包
✨做一次按NLP项目常见工具的使用拆解 1. tokenizer from torchtext.data.utils import get_tokenizertokenizer get_tokenizer(basic_english) text_sample "Were going on an adventure! The weather is really nice today." tokens tokenizer(text_sample) p…...