小朋友排成一排，老师给他们分苹果。 小朋友从左到右标号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
代码语言：javascript复制#include<stdio.h>
#define N 100004
typedef struct Node{
int l,r,v;
} L;
L node[N*4]; //线段树的每个节点 其中包括三个参数 l为线段左端点的值 r:线段右端点的值 v：该节点所存储的值
void Init(int now,int le,int ri){ //构建线段树 并将结点的值初始化全部为0
if(le==ri){
node[now].l=le;
node[now].r=ri;
node[now].v=0;
return;
}//如果线段的左端点==线段的右端点 那么即是最后的叶子结点 return
int mid=(le ri)>>1; //求出中点
int next=now<<1; //将结点的序号*2即下一代节点（子结点）序号；
Init(next,le,mid); //构建左子树(左区域 ）
Init(next 1,mid 1,ri); //构建右子树(右区域 ）
node[now].l=le; //给当前结点的线段左右端点赋值
node[now].r=ri;
node[now].v=0; //给结点赋值
}
void f(int now,int le,int ri,int add){ //在线段树中寻找对应的区间 给对应该区间的结点加上该发的
//苹果数，即为在那个结点下的所有的子节点的区间里的小孩均会被发苹果。 （pinrt函数中会提到）
if(node[now].l==le&&node[now].r==ri){
node[now].v =add;
return;
} //给对应该区间的结点加上发的苹果数
int mid=(node[now].l node[now].r)>>1;//求出中点
int next=now<<1; //结点的序号*2(找到子节点）
if(ri<=mid){
f(next,le,ri,add); //如果寻找的区间的右端点小于中点 则在左边寻找
}
else if(le>mid){
f(next 1,le,ri,add); //反之在右边寻找
}
else
{
f(next,le,mid,add); //如果横跨两边 左右两边都寻找
f(next 1,mid 1,ri,add);
}
}
void out(int now){
if(node[now].l==node[now].r){
printf("%d ",node[now].v);
return;
} //如果是最后的叶子结点 输出小朋友的苹果总数
int next=now<<1;
//父亲的范围大 包含的儿子结点的区间 所以父亲下面儿子结点也要加上父亲结点被发的苹果数
node[next].v =node[now].v;
out(next);
node[next 1].v =node[now].v;
out(next 1);
}
int main(){
int n,m,i,a,b,c;
while(scanf("%d%d",&n,&m)!=EOF){
Init(1,1,n);
for(i=0;i<m;i ){
scanf("%d%d%d",&a,&b,&c);
f(1,a,b,c);
}
out(1);
}
return 0;
}
