2019-03-05 [蓝桥杯]分苹果-差分数组

题目描述
小朋友排成一排，老师给他们分苹果。
小朋友从左到右标号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 6 5 3 3

超时间了，想用离散化弄一下，但是好像是使用线段树。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100001;
vector<int>bound;
int c[maxn],L[maxn],R[maxn];
int n,m;
LL res[maxn];

int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> L[i] >> R[i] >> c[i];
        bound.push_back(L[i]);
        bound.push_back(R[i]);
        if(L[i]>1) bound.push_back(L[i]-1);
        if(R[i]<n) bound.push_back(R[i]+1);
    }
    bound.push_back(1);
    bound.push_back(n);
    sort(bound.begin(),bound.end());
    bound.erase(unique(bound.begin(),bound.end()),bound.end());
    for(int i=0;i<bound.size();i++) cout << bound[i]<<" ";
    cout << endl; 
    for(int i=1;i<=m;i++)
    {
        int s=find(bound.begin(),bound.end(),L[i])-bound.begin();
        int e=find(bound.begin(),bound.end(),R[i])-bound.begin();
        for(int j=s;j<=e;j++) res[j]+=c[i];
    }
    int cnt = bound.size();
    for(int i=0;i+1<cnt;i++)
    {
        int num = bound[i+1]-bound[i];
        if(i+1==cnt-1) num++;
        for(int j=0;j<num;j++) cout << res[i] << " ";
    }
    return 0;
}

使用差分数组，感觉和线段树有点相似

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100001;
int A[maxn],d[maxn];
int main(void)
{
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int L,R,C;
        cin >> L >> R >> C;
        d[L]+=C;
        d[R+1]-=C;
    }
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            A[i]=d[i];
            cout << A[i];
        }
        else 
        {
            A[i]=A[i-1]+d[i];
            cout << A[i];
        }
        if(i!=n) cout << " ";
    }
    return 0;
}