2.一維差分 - 藍橋云課

問題描述

給定一個長度為?n?的序列?a。

再給定?m?組操作，每次操作給定 3 個正整數?l,?r,?d，表示對?a_{l}?到?a_{r}?中的所有數增加?d。

最終輸出操作結束后的序列?a。

??Update??: 由于評測機過快，n,?m?于 2024-12-09 從?102?加強至?2×105，杜絕暴力通過本題。

輸入格式

第一行輸入兩個正整數?n,?m。(1≤n,m≤2×105)

第二行輸入?n?個正整數?a。(1≤i≤n,1≤ai?≤104)。

接下來?m?行，每行輸入 3 個正整數?l,?r,?d。(1≤l≤r≤n,?104≤d≤104)。

輸出格式

輸出?n?個整數，表示操作結束后的序列?a。

樣例輸入

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

樣例輸出

3 4 5 3 4 2

思路：

模板

代碼:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+10;
int a[N],diff[N];
int main() 
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin >> n >> m;for(int i = 1 ; i <= n ; i++){cin >> a[i];diff[i] = a[i] - a[i-1];}while(m--){int l,r,d;cin >> l >> r >> d;diff[l] += d;if(r + 1 <= n)diff[r+1] -= d;}//復原for(int i = 1 ; i <= n ; i++)diff[i] += diff[i-1]; for(int i = 1 ; i <= n ; i++)cout << diff[i] << " ";return 0;
}