DP37【模板】差分

​

给你一个长度为n的正数数组$a_1,a_2,…a_n $

接下来对这个数组进行m次操作，每个操作包含三个参数l,r,k，代表将数组中$a_l,…a_r$部分都加上k。

请输出操作后的数组。

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e5+100;
typedef long long ll;
ll a[N];
ll dp[N];
int main(void) {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
         
    }
    while(m--) {
        int l,r,x;
        cin>>l>>r>>x;
        dp[l] += x;
        dp[r+1] -=x;
    }   
    for(int i=1;i<=n;i++) dp[i] += dp[i-1];
    for (int i=1;i<=n;i++) 
          printf("%lld ",a[i] + dp[i]);
    puts("");
    
    
    return 0;
}