差分

我不是女神ヾ 2021-11-01 10:04 443阅读 0赞

概念

对于一个数组a[n]，有m次操作，都是对区间[l,r]加上k，完事后输出数组

在知道第一个数a[1]的情况下，如果我们知道后面的数与前一个数的差值p，那么就能还原原数组，即

  1. for(int i = 2; i <= n; ++i) a[i] = a[i - 1] + p[i];//还原
  3. for(int i = 1; i <= n; ++i) p[i] = a[i] - a[i - 1];//get p

细节

对于区间操作，一个区间都加上k，即最左边的数a[l]比它前一位多了k，即p[l] += k;

最右边的数a[r]比它后一位多了k，则它后一位比它少了k，即p[r + 1] -= k;

区间内各个数之间的差值不变，例如1和2差1，都加上5变成6和7，还是差1，所以只是改两端即可。

代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 100001;
  7. int n,m;
  8. int a[N],pl[N];
  10. int main(){
  11.     cin >> n >> m;
  12.     for(int i = 1; i <= n; ++i) cin >> a[i];
  13.     for(int i = 1; i <= n; ++i) pl[i] = a[i] - a[i - 1];
  14.     for(int i = 1, z, l, r, y; i <= m; ++i){
  15.         cin >> z >> l >> r >> y;
  16.         if(z == 1){
  17.             pl[l] += y;
  18.             pl[r + 1] -= y;
  19.         }
  20.         for(int i = 1; i <= n; ++i) a[i] = a[i - 1] + pl[i];
  21.         for(int i = 1; i <= n; ++i) cout << a[i] << " "; 
  22.     }
  23.     return 0;
  24. }

#

转载于:https://www.cnblogs.com/Adventurer-H/p/11230189.html

发表评论

表情：
评论列表 （有 0 条评论，443人围观）

还没有评论，来说两句吧...

相关阅读

    相关 差分信号解释

     所谓差分方式传输，就是发送端在两条信号线上传输的幅值是相等的，相位是相反的电信号，如下图所示： ![20171222175545054][]        而对于接收端，

    小咪咪小咪咪/ 0 赞/ 352 阅读

    相关 差分

    概念 对于一个数组a\[n\]，有m次操作，都是对区间\[l,r\]加上k，完事后输出数组 在知道第一个数a\[1\]的情况下，如果我们知道后面的数与前一个数的差值p，

    我不是女神ヾ我不是女神ヾ/ 0 赞/ 444 阅读

    相关 差分 & 前缀和

    我们从问题入手。   入门问题：有已赋值的 n 个数，现在有 m 个指令 操作 1： 每一次要求将第 k 个数加上 a； 操作 2： 查询第 k 个数字的值。 $1 

    怼烎@怼烎@/ 0 赞/ 473 阅读