差分例題 分蘋果

時間限制: 1Sec 記憶體限制: 128MB 送出: 231 解決: 69

題目描述

小朋友排成一排，老師給他們分蘋果。

小朋友從左到右标号1…N。有M個老師，每次第i個老師會給第Li個到第Ri個，一共Ri-Li+1個小朋友每人發Ci個蘋果。

最後老師想知道每個小朋友有多少蘋果。

資料規模和約定

100%的資料，N、M≤100 000，1≤Li≤Ri≤N，0≤Ci≤100。

輸入

第一行兩個整數N、M，表示小朋友個數和老師個數。

接下來M行，每行三個整數Li、Ri、Ci，意義如題目表述。

輸出

一行N個數，第i個數表示第i個小朋友手上的水果。

樣例輸入

5 3

1 2 1

2 3 2

2 5 3

1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 const int maxn = 100000;
 5 int d[maxn];
 6 int main()
 7 {
 8     int n,m;
 9     int a,b,c;
10     cin>>n>>m;
11     while(m--){
12         cin >> a>> b>> c;
13         d[a] += c;
14         d[b+1] -= c;
15     } 
16     for(int i = 1; i <= n; i++){
17         d[i] += d[i-1];
18         cout << d[i]<<' ';
19     }
20     return 0;
21 }