AcWing - 差分(一维差分)
发布日期:2021-07-01 00:21:51
浏览次数:2
分类:技术文章
本文共 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月21日 23时57分12秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Spring Security Oauth2 如何增加自定义授权模式
2019-05-01
logback + Kafka + logstash 集成
2019-05-01
在SpringBoot1.5.x下如何使RedisTokenStore集群化
2019-05-01
Spring Cloud Consul应用下线后,健康检查自动删除无效服务
2019-05-01
spring cloud consul 应用的多实例名的解决
2019-05-01
kafka设置某个topic的数据过期时间
2019-05-01
linux系统编程之信号(五):实时信号与sigqueue函数
2019-05-01
225. 用队列实现栈
2019-05-01
linux系统编程之信号(六):竞态条件与sigsuspend函数
2019-05-01
124. 二叉树中的最大路径和
2019-05-01
LeetCode 148:排序链表 【归并】
2019-05-01
LeetCode 560 和为 k 的子数组
2019-05-01
LeetCode 581 最短无序连续子数组
2019-05-01
Java Stream 使用
2019-05-01
Flink 的DataStream 和 DataSet区别
2019-05-01
Flink源码学习
2019-05-01
MYSQL 表的手动更新统计分析记录
2019-05-01
MYSQL的身体,POSTGRESQL 的头脑
2019-05-01