蓝桥杯算法提高VIP-分苹果 （C++代码）

解题思路:
在网上找了一个不用线段树而用差分数组求解的，看完后感觉智商是被狠狠地碾压了（＞﹏＜）

言归正传，所谓差分数组，就是说假设有两个数组d[i],a[i],d[i]=a[i]-a[i-1],d[0]=a[0],那么d[i]就是a[i]的差分数组，d[i]的前缀和就是a[i],即a[i]=d[i]+d[i-1]+...+d[0];

本题中，发苹果的方式是连续的，那么每次改变的差分数组只有d[l]和d[r+1],连续m次，

最后根据上述公式可以求出每个小朋友得到的苹果。

其实差分数组求和的原理就是数学上的裂项相消，可以说并不困难，可我就是没能想到，我能说什么呢！

参考代码：

#include<iostream>
using namespace std;
int d[100005]; //d[i]表示第i个小朋友比第i-1个小朋友多的苹果
int main()
{
    int n,m,l,r,c;
    cin>>n>>m;
    while(m--){
        cin>>l>>r>>c;
        d[l]+=c;    //每一次发苹果第l个小朋友比第l-1个小朋友多c个，
        d[r+1]-=c;  //第r+1个小朋友比第r个小朋友少c个。
}
    for(int i=1;i<=n;i++){
        d[i]+=d[i-1];   //根据差分数组的性质进行求和
        cout<<d[i]<<" ";
    }
    cout<<endl;
    return 0;
}