242. 一个简单的整数问题
Powered by:NEFU AB-IN
Link
文章目录
- 242. 一个简单的整数问题
- 题意
- 思路
- 代码
242. 一个简单的整数问题
-
题意
给定长度为 N的数列 A,然后输入 M行操作指令。
第一类指令形如 C l r d,表示把数列中第 l∼r个数都加 d
第二类指令形如 Q x,表示询问数列中第 x个数的值。
对于每个询问,输出一个整数表示答案 -
思路
树状数组 + 差分,实现区间修改 + 单点查询
其实就是对差分数组进行原先树状数组的操作,维护差分数组- 区间修改就是
add(l, d) add(r + 1, -d) - 单点查询就是,对差分数组求前缀和,也就是单点查询了
如要实现区间查询,详见 link
- 区间修改就是
-
代码
''' Author: NEFU AB-IN Date: 2023-03-26 11:48:05 FilePath: \Acwing\242\242.py LastEditTime: 2023-03-26 11:55:10 ''' # import import sys, math from collections import Counter, deque from heapq import heappop, heappush from bisect import bisect_left, bisect_right# Final N = int(1e5 + 10) INF = int(2e9)# Define sys.setrecursionlimit(INF) read = lambda: map(int, input().split())# —————————————————————Division line ———————————————————————————————————————— tr = [0] * Ndef lowbit(x):return x & -xdef add(x, v):while x < N:tr[x] += vx += lowbit(x)def query(x):res = 0while x:res += tr[x]x -= lowbit(x)return resn, m = read() a = [0] + list(read()) for i in range(1, n + 1):add(i, a[i] - a[i - 1])for _ in range(m):op = list(input().split())if op[0] == 'C':l, r, d = map(int, op[1:])add(l, d)add(r + 1, -d)else:print(query(int(op[1])))
相关文章:
242. 一个简单的整数问题
Powered by:NEFU AB-IN Link 文章目录242. 一个简单的整数问题题意思路代码242. 一个简单的整数问题 题意 给定长度为 N的数列 A,然后输入 M行操作指令。 第一类指令形如 C l r d,表示把数列中第 l∼r个数都加 d 第二类指令形如 Q x,表示询问…...
docker安装Redis高可用(一主二从三哨兵)
本次教程使用docker swarm安装 准备三台机器 hostIP用途node1192.168.31.130redis-master01,redis哨兵节点01node2192.168.31.131redis-slave01, redis哨兵节点02node3192.168.31.132redis-slave02 redis哨兵节点02 注意事项: 1:需要保证三…...
安全防御之入侵检测篇
目录 1.什么是IDS? 2.IDS和防火墙有什么不同?3.IDS的工作原理? 4.IDS的主要检测方法有哪些?请详细说明 5.IDS的部署方式有哪些? 6.IDS的签名是什么意思?签名过滤器有什么用?例外签名的配置作…...
学习系统编程No.10【文件描述符】
引言: 北京时间:2023/3/25,昨天摆烂一天,今天再次坐牢7小时,难受尽在不言中,并且对于笔试题,还是非常的困难,可能是我做题不够多,也可能是没有好好的总结之前做过的一些…...
网络基础认识
目录 一、计算机网络背景 1.1 网络发展 1.2 "协议"由来 二、网络协议初识 2.1 协议分层 2.2 OSI七层模型 2.3 TCP/IP五层模型 三、网络协议栈 四、数据包封装与分用 五、网络传输基本流程 5.1 同局域网的两台主机通信 5.2 跨网络的两台主机通信 六、网络…...
【蓝桥杯_练习】
蓝桥杯1.创建工程2.LED灯点亮led.c3.LCD液晶屏显示lcd.c4.定时器按键单机interrupt.hinterrupt.cman.c5.定时器(长按键)interrupt.hinterrupt.cmain.c6.PWMmain.c7.定时器-输入捕获(频率,占空比测量)interrupt.cmain.c…...
【C语言蓝桥杯每日一题】——跑步锻炼
【C语言蓝桥杯每日一题】—— 跑步锻炼😎前言🙌排序🙌总结撒花💞😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介…...
Qt之实现类似软件安装时的新功能介绍界面
一.效果 在软件安装时,一般会轮播软件的新功能,安装后,如果还想查看这些新功能该怎么办呢,我们可以把这个介绍新新功能的小应用集成到软件的“帮助”菜单中,比起纯黑文字的无趣介绍,图文方式的呈现会生动得多。 最近在看《赘婿》,借几张图过来用用。 二.原理 1.分层结…...
echarts地图不同地区设置不同的颜色
var myChart ec.init(document.getElementById(main));let option {tooltip: {trigger: item,},dataRange: {//左下角的颜色块。start:值域开始值;end:值域结束值;label:图例名称;color:自定义…...
网易云音乐API部署Vercel获取接口过程
前提:部署自己的网易云接口主要用途在于在完成前端的仿网易云播放器的时候,根据自己部署的接口可以用于获取数据。大体流程是通过在github上fork别人的API接口项目,然后在Vercel部署即可获得自己的网易云后端数据接口了,不过根据我…...
Java基础:字符串(String)及常用操作
目录 字符串的声明及创建 字符串的操作 连接字符串(或concat) 获取字符串的长度 length 查找字符串 indexOf 获取字符串某个位置的字符 charAt 查询某个字符串是否存在 contains 截取字符串 substring(一) 截取字符串 su…...
FL Studio 21中文版支持主题随心换,FL Studio 21Mac版新增对苹果M2/1家族芯片原生支持。
FL Studio 21.0.0 官方中文版重磅发布 纯正简体中文支持,更快捷的音频剪辑及素材管理器,多样主题随心换! Mac版新增对苹果M2/1家族芯片原生支持。 更新版本:21.0.0支持语言:简体中文/英语更新时间:2022.12…...
【蓝桥杯集训·周赛】AcWing 第96场周赛
文章目录第一题 AcWing 4876. 完美数一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第二题 AcWing 4877. 最大价值一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第三题 AcWing 4878. 维护数组一、题目1、原…...
【数据结构】顺序表的深度刨剖析
前言:在上一篇文章中,我们已经对数据结构有了一定了解,我们可以通过优化空间复杂度或者时间复杂度从而提高我们程序运行或存储速率。至此我们就知道了数据结构的重要性,所以今天我们将要了解和学习一种实用的数据结构——线性表。…...
Unity 之 使用原生UGUI实现随手移动摇杆功能经典实例
Unity 之 使用原生UGUI实现随手移动摇杆功能实现效果一,实现思路1.1 原理解析1.2 思路概述二,实现代码2.1 随手落下2.2 摇杆转动三,源码分享3.1 场景搭建3.2 完整代码3.3 实现效果实现效果 本文最终实现效果: 一,实现…...
Linux内核源代码概述
Linux内核源代码非常庞大,截止到2015年据统计代码总量就已经超过1500万行(LOC,Line of Code),看代码总量非常吓人,具体看这1500万行代码的大致分布情况如下图。 显然占比最大的drivers和arch目录下的代码合…...
Nginx 教程-动静分离
一、Nginx 动静分离理论1、概念今天学习和梳理Nginx动静分离,动静分离是将网站静态资源(HTML,JavaScript,CSS,img等文件)与后台应用分开部署,之所以要进行动静分离,其一为了提高前端…...
自己设计的网站,如何实现分页功能?(详细代码+注释)
目录 前言 实现分页功能 需求分析 客户端开发 服务器开发 前后端交互——两种前端得到 文章总页数 的方法,那种更合适? 前言 你在设计网站的时候是否有过这样的烦恼:“我设计的网站怎么就是从上到下一条线内容全部展开,一点都…...
STM32F407控制微型推拉式电磁铁(通过继电器)
1、继电器 继电器相当于开关,单片机通过io口高低电平的控制来控制继电器的开闭。采用继电器的好处除了能够用低电压控制高电压(如32单片机控制220V的电压)外,还可以防止电流反冲,弄烧单片机。 本文采用3.3v的电磁铁&am…...
VS Code工作区用法
背景VS Code可以通过"文件/打开文件夹"来打开本地项目,但是想要打开多个项目便需要来回切换,比较费劲。此时就可以使用工作区功能,将不同的项目放置到同一个工作区中,这样切换项目的时候就会非常方便。操作方法打开其中…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
