首页 > 编程语言 >基础算法(十)差分模板---以题为例

基础算法(十)差分模板---以题为例

时间:2024-02-03 15:23:25浏览次数:29  
标签:insert 包含 int 整数 --- 差分 序列 模板 1000

输入一个长度为 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−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

#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];

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

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(i,i,a[i]);}
        
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i =1;i<=n;i++){b[i]+=b[i-1];
    cout<<b[i]<<" ";}
}

 

 

标签:insert,包含,int,整数,---,差分,序列,模板,1000
From: https://www.cnblogs.com/Ghost-Knight/p/18004808

相关文章

  • 2022CCPC女生赛-L.彩色的树(线段树合并)
     链接Problem-L-Codeforces以前迷迷糊糊用dsuontree写的题目但是其实没搞明白现在换一种写(太菜了还是没搞明白dsuontree)题意:给你一棵树,询问给定询问的节点上,子树内距离小于等于k的节点不同颜色的种类有多少个。k是固定的值。解法:本题做法为比较板子的线段树合并,......
  • FreeRTOS--软件定时器
    示例源码基于FreeRTOSV9.0.0软件定时器1.概述软件定时器用来在未来某个时间点执行某个动作,或者周期性地执行某个动作;软件定时器的实现依赖于系统滴答中断。2.设计原理定时器分为单次定时器和周期定时器,定时时间到执行注册的回调函数。单次定时器触发后即睡眠(不会销毁,依旧......
  • q-binomial
    q-binomial\[[n]_q=\sum\limits_{i=0}^{n-1}q^i=\lim_{x\rightarrowq}\frac{1-x^n}{1-x},[n]!_q=\prod_{i=1}^n[i]_q,{n\brackm}_q=\frac{[n]!_q}{[m]!_q[n-m]!_q}\\{n\brackm}_q={n-1\brackm-1}_q+q^m{n-1\brackm}_q\......
  • C语言“->“和“p->next“的理解
    这是对"->"的理解在c语言中,"->"是结构体指针的运算符.它允许你通过指向结构体的指针来访问结构体中的成员.例如,以下定义了一个student类的结构体,其中包含两个字符串类型的成员:"name","id",以及一个整形成员"age",可以使用如下方式访问结构体成员:structstudent{c......
  • 无涯教程-slice()函数
    slice()方法选取数组的一部分,并返回一个新数组。slice()-语法array.slice(begin[,end]);begin  - 从零开始的索引。作为负索引,start表示从序列结尾开始的偏移量。end    - 从零开始的索引,终止提取。slice()-返回值根据传递的参数返回提取的数......
  • csi-driver-nfs持久化
    1.简介csi-driver-nfs是一个用于Kubernetes的NFSCSI驱动程序,它可以让Kubernetes访问Linux节点上的NFS服务器。它的CSI插件名称是nfs.csi.k8s.io。这个驱动程序需要已经存在并配置好的NFSv3或NFSv4服务器,它支持通过创建NFS服务器下的新子目录来动态分配持久......
  • 基础算法(九)二维前缀和模板---以题为例
    输入一个 n 行 m的整数矩阵,再输入q 个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。输入格式第一行包含三个整数 n,m,q。接下来 n行,每行包含m 个整数,表示整数矩阵。接下来 q 行,每行包含四个......
  • 第一篇-安装工程专业基础知识
      1.电气:强电弱电,强电比如有电力电缆,比较粗,弱电有控制电缆细,强电频率低,弱电频率大弱电主要处理对象是信息,强电主要处理对象是能源(电力) ......
  • 对称字符串-od-python
    题目描述对称就是最大的美学,现有一道关于对称字符串的美学。已知:第1个字符串:R第2个字符串:BR第3个字符串:RBBR第4个字符串:BRRBRBBR第5个字符串:RBBRBRRBBRRBRBBR相信你已经发现规律了,没错!就是第个字符串=第i-1号字符串取反+第i-1号字符串取反(R->B,B->R)现在告诉你n......
  • ICLR 2024 | Mol-Instructions: 面向大模型的大规模生物分子指令数据集
    Mol-Instructions:面向大模型的大规模生物分子指令数据集 发表会议:ICLR2024论文标题:Mol-Instructions:ALarge-ScaleBiomolecularInstructionDatasetforLargeLanguageModels论文链接:https://arxiv.org/pdf/2306.08018.pdf代码链接:https://github.com/zjunlp/Mol......