AcWing - 差分(一维差分)
发布日期:2021-07-01 00:21:51
浏览次数:3
分类:技术文章
本文共 1331 字,大约阅读时间需要 4 分钟。
题目链接:
时/空限制:1s / 64MB题目描述
输入一个长度为n的整数序列。
接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数,表示整数序列。
接下来m行,每行包含三个整数l,r,c,表示一个操作。
输出格式
共一行,包含n个整数,表示最终序列。
数据范围
1≤n,m≤100000,
1≤l≤r≤n, −1000≤c≤1000, −1000≤整数序列中元素的值≤1000输入样例
6 3
1 2 2 1 2 1 1 3 1 3 5 1 1 6 1
输出样例
3 4 5 3 4 2
解题思路
题意:给你一个序列和q次查询,每次查询可以将区间[l, r]内的数都加上c,求最终的序列。
思路:首先我们来介绍一下差分是什么东西:1. 差分定义
- 定义一个差分数组S和一个原数组A。
- p[1]=a[1], p[i]=a[i]-a[i-1]
2. 差分性质
- A数组的差分数组的前缀和数组就等于原数组,即S[i]=a[i]=p[i]+S[i-1]
- S数组的差分数也等于差分数组,即p[i]=S[i]-S[i-1]
- 还有比较重要,而且常用的的一条,我们在修改某一段区间的时候,比如这道题的集体加 e 的时候,将操作放在差分数组上就变成了p[l]+=e,p[r+1]-=e这样,我们就可以把区间操作更改为单点操作,很大的减少了时间复杂度。
- 当然,差分的运用远不止于此,在树上等也是可以进行差分操作的。
综上:有了这些性质,我们在做一些题的时候就可以将其转换为差分数组求解,完成过后过一遍前缀和得到正确答案。
这道题就是首先构造出一个差分数组,然后就是q次更新了,更新完之后求一下前缀和就行了。
Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;const int MAXN = 100005;int spt[MAXN], bits[MAXN];int main() { int n, q; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &spt[i]); bits[i] = spt[i] - spt[i - 1]; } while (q--) { int l, r, v; scanf("%d%d%d", &l, &r, &v); bits[l] += v; bits[r + 1] -= v; } for (int i = 1; i <= n; i++) { bits[i] += bits[i - 1]; printf("%d%c", bits[i], "\n "[i != n]); } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/99856192 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月25日 07时06分24秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
SpringBoot内置Tomcat配置参数
2019-04-30
ubuntu 快捷键
2019-04-30
linux 根目录下文件夹分析
2019-04-30
linux 查看分区和文件大小
2019-04-30
Not using PCAP_FRAMES 解释(snort中)
2019-04-30
技术转管理?这些“坑”你要绕道走
2019-04-30
领域驱动设计(DDD)前夜:面向对象思想
2019-04-30
Camera驱动调试小记
2019-04-30
四线触摸屏原理
2019-04-30
C/C++如何返回一个数组/指针
2019-04-30
腾讯AI语音识别API踩坑记录
2019-04-30
YbtOJ——递推算法【例题4】传球游戏
2019-04-30
安装openrave 0.9的各种依赖包
2019-05-01
kpm代码使用细节
2019-05-01
@FeignClient注解的重复名称解决
2019-05-01
java.net.BindException: 无法指定被请求的地址
2019-05-01
scala list
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01