【高级数据结构】线段树
目录
最大数(单点修改,区间查询)
线段树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驱动开发:模块_引用符号
目录 🍅点击这里查看所有博文 随着自己工作的进行,接触到的技术栈也越来越多。给我一个很直观的感受就是,某一项技术/经验在刚开始接触的时候都记得很清楚。往往过了几个月都会忘记的差不多了,只有经常会用到的东西才有可能真正记…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...

Mac flutter环境搭建
一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...
CppCon 2015 学习:Simple, Extensible Pattern Matching in C++14
什么是 Pattern Matching(模式匹配) ❝ 模式匹配就是一种“描述式”的写法,不需要你手动判断、提取数据,而是直接描述你希望的数据结构是什么样子,系统自动判断并提取。❞ 你给的定义拆解: ✴ Instead of …...
PostgreSQL 对 IPv6 的支持情况
PostgreSQL 对 IPv6 的支持情况 PostgreSQL 全面支持 IPv6 网络协议,包括连接、存储和操作 IPv6 地址。以下是详细说明: 一、网络连接支持 1. 监听 IPv6 连接 在 postgresql.conf 中配置: listen_addresses 0.0.0.0,:: # 监听所有IPv4…...