題目描述
小朋友排成一排山卦，老師給他們分蘋(píng)果。
小朋友從左到右標(biāo)號(hào)1..N刽脖。有M個(gè)老師，每次第i個(gè)老師會(huì)給第Li個(gè)到第Ri個(gè)忌愚，一共Ri-Li+1個(gè)小朋友每人發(fā)Ci個(gè)蘋(píng)果。
最后老師想知道每個(gè)小朋友有多少蘋(píng)果却邓。

數(shù)據(jù)規(guī)模和約定
100%的數(shù)據(jù)硕糊，N、M≤100 000腊徙，1≤Li≤Ri≤N简十，0≤Ci≤100。

輸入
第一行兩個(gè)整數(shù)N撬腾、M螟蝙，表示小朋友個(gè)數(shù)和老師個(gè)數(shù)。
接下來(lái)M行民傻，每行三個(gè)整數(shù)Li胰默、Ri场斑、Ci，意義如題目表述牵署。
輸出
一行N個(gè)數(shù)漏隐，第i個(gè)數(shù)表示第i個(gè)小朋友手上的水果。
樣例輸入
5 3
1 2 1
2 3 2
2 5 3
樣例輸出
1 6 5 3 3

超時(shí)間了奴迅，想用離散化弄一下青责，但是好像是使用線段樹(shù)。

#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;
}

使用差分?jǐn)?shù)組取具，感覺(jué)和線段樹(shù)有點(diǎn)相似

#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;
}