算法提高 分苹果 时间限制：1.0s 内存限制：256.0MB 提交此题 问题描述 小朋友排成一排，老师给他们分苹果。 小朋友从左到右标号1..N。有M个老师，每次第i个老师会给第Li个到第Ri个，一共Ri-Li+1个小朋友每人发Ci个苹果。 最后老师想知道每个小朋友有多少苹果。 输入格式 第一行两个整数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 数据规模和约定 40%的数据，N、M≤1 000。 100%的数据，N、M≤100 000，1≤Li≤Ri≤N，0≤Ci≤100。
/* 思路：O(n*m)的纯循环模拟肯定超时 所以用线段树，先初始化所有节点为0 从根节点更新插入的节点，最后结束后再一次性输出并从上到下更新 */ #include <iostream> #include <string.h> #include <algorithm> #include <cstdio> #include <math.h> using namespace std; const int N=100000+10; struct Node{ int l,r,v; }node[N*4]; 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; } int mid=(le+ri)>>1; int ne=now<<1; Init(ne,le,mid); Init(ne+1,mid+1,ri); node[now].l=le; node[now].r=ri; node[now].v=0; } void insert(int now,int le,int ri,int add){ //插入数据 if(node[now].l==le&&node[now].r==ri){ node[now].v+=add; return; } int mid=(node[now].l+node[now].r)>>1; int ne=now<<1; if(ri<=mid){ insert(ne,le,ri,add); } else if(le>mid){ insert(ne+1,le,ri,add); } else { insert(ne,le,mid,add); insert(ne+1,mid+1,ri,add); } } void print(int now){ if(node[now].l==node[now].r){ cout<<node[now].v<<" "; return; } int ne=now<<1; node[ne].v+=node[now].v; print(ne); node[ne+1].v+=node[now].v; print(ne+1); } int main(){ int n,m,i,a,b,c; while(cin>>n>>m){ Init(1,1,n); for(i=0;i<m;i++){ cin>>a>>b>>c; insert(1,a,b,c); } print(1); cout<<endl; } return 0; }