每日打卡day8——差分练习

这篇具有很好参考价值的文章主要介绍了每日打卡day8——差分练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

输入一个长度为 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
思路:差分模板套用,对[ L, R] 区间进行增加或减小,都可以转 该数组的差分数组(即前缀和为该位置原本值)的第 L 位置增加或减少 C, 再对 R 位置减少或增加 C, 最后,对该差分数组进行前缀和,即得到修改后的数组值

代码如下:文章来源地址https://www.toymoban.com/news/detail-585322.html

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 10;

int n, m;
vector<int> nums(N, 0);
vector<int> res(N, 0);

void insert(int l, int r, int c){
    res[l] += c;
    res[r + 1] -= c;
}

int main(){
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        cin >> nums[i];
    }
    
    //求差分数组
    for(int i = 1; i <= n; i++){
        insert(i, i, nums[i]);
    }
    
    while(m--){
        int l = 0, r = 0, c = 0;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    
    for(int i = 1; i <= n; i++){
        res[i] += res[i - 1];
        cout << res[i] << " ";
    }
    
    return 0;
}
 

到了这里,关于每日打卡day8——差分练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日算法打卡:连号区间数 day 18

    1210. 连号区间数 题目难度:简单 题目来源:第四届蓝桥杯省赛C++ B组,第四届蓝桥杯省赛Java B组 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1 ∼ N 1 sim N 1 ∼ N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [ L , R ] [L, R] [ L , R ] 里的

    2024年01月19日
    浏览(57)
  • 每日算法打卡:机器人跳跃 day 11

    730. 机器人跳跃问题 题目难度:中等 题目来源:笔试题 机器人正在玩一个古老的基于 DOS 的游戏。 游戏中有 N+1 座建筑——从 0 到 N 编号,从左到右排列。 编号为 0 的建筑高度为 0 个单位,编号为 iii 的建筑高度为 H ( i ) H(i) H ( i ) 个单位。 起初,机器人在编号为 0 的建筑处

    2024年01月23日
    浏览(82)
  • 数据结构day8(2023.7.25)

    排序:把无需序列转换为有序序列的一种算法。 内排:在计算机内存中实现的排序算法【多用适用于数据量较小的情况】 外排:在计算机内存以及外部介质实现的排序算法【先内存,在外部】 排序的分类: 交换排序:冒泡排序、快速排序 插入排序:直接插入排序,希尔排

    2024年02月15日
    浏览(36)
  • C语言练习day8

    变种水仙花_牛客题霸_牛客网 题目: 思路:我们拿到题目的第一步可以先看一看题目给的例子,1461这个数被从中间拆成了两部分:1和461,14和61,146和1,不知道看到这大家有没有觉得很熟悉的样子,没错,它拆分的时候是按照每一位来逐渐往右增加来拆分的,换数学中的说

    2024年01月21日
    浏览(39)
  • C语言:选择+编程(每日一练Day8)

    目录 选择题:  题一: 题二: 题三: 题四: 题五: 编程题: 题一:字符个数统计 思路一: 题二:多数元素 思路一:  本人实力有限可能对一些地方解释和理解的不够清晰,可以自己尝试读代码,或者评论区指出错误,望海涵! 感谢大佬们的一键三连! 感谢大佬们的一

    2024年02月11日
    浏览(88)
  • 数据结构的练习day1

    链表只能一个一个的遍历,不能通过随机访问来获取节点 链表的地址是并要求连续的,是通过内部的指针来进行联系的

    2024年04月22日
    浏览(34)
  • 数据结构的练习day2(未完待续)

    数据结构线性结构之单向循环链表的基本操作

    2024年04月24日
    浏览(35)
  • 数据结构算法练习 插入排序 冒泡排序

    插入排序 代码如下  package main import \\\"fmt\\\" func main() {     a := []int{4, 5, 6, 1, 3, 2}         b := insert(a)     for i := 0; i len(b); i++ {         fmt.Println(b[i])     } } func insert(a []int) []int {     if len(a) = 1 {                   如果数组长度小于等于1 不用排序直接返回          retur

    2024年02月08日
    浏览(55)
  • 数据结构与算法系列之习题练习

    💗 💗 博客:小怡同学 💗 💗 个人简介:编程小萌新 💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞 括号匹配问题。 用队列实现栈。 用栈实现队列。 设计循环队列。 有效的括号 //用栈来实现 //左括号进栈 右括号出栈并销毁如果不匹配则return //设置两个队列,入栈

    2024年02月11日
    浏览(46)
  • Linux每日练习day3

    创建1个f开头的文件夹,2个f开头的普通文件 1、输出文件名时,每个文件名前加一个前缀abc 2、输出所有文件名时,在行头加一个前缀 aaa 2、通过批量处理的命令 exec或者xargs 删除f开头的普通文件 1、过滤出etc目录中以p开头的文件名 2、过滤出etc下passwd这个文件内容中包含字母

    2024年03月13日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包