AcWing 797 差分 一维差分 c/c++实现

你的名字 2022-12-22 04:38 244阅读 0赞

原题链接：AcWing 797 差分

题目描述：给出 n 个整数和 m 个操作，每个操作输入三个数 l、r、v，表示将区间 [l,r] 中的每个数加上v。问最终数列中每个数是多少。
1 ≤ n,m ≤ 100000,
1≤ l ≤ r ≤ n,
−1000 ≤ c ≤ 1000,

输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：
3 4 5 3 4 2

思路： 这就是用一个差分数组快速的实现对一个区间的修改。我们用一个b数组（初始化为0）来记录，若对区间 [l,r] 加c，我们可以给b[l] + c，给b[r+1] - c，修改后的a[i]就是原数组的a[i]加上b数组1到i的和，差分详见此处。
证明如下：
yxcnb
ac代码：

  1. #include<iostream>
  2. using namespace std;
  3. const int N = 100010;
  5. int a[N],b[N],n,m,l,r,c;
  6. int main()
  7. { 
  8.     cin >> n >> m;
  9.     for(int i = 1;i <= n;i++)
  10.         cin >> a[i];
  11.     for(int i = 0;i < m;i++)
  12.     { 
  13.         cin >> l >> r >> c;
  14.         b[l] += c;
  15.         b[r+1] -= c;
  16.     }
  17.     for(int i = 1;i <= n;i++)
  18.     { 
  19.         b[i] += b[i-1];
  20.         cout << a[i]+b[i] << " ";
  21.     }
  23.     return 0;
  24. }

发表评论

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

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

相关阅读

    相关 差分

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

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