解题思路:
- 这个题解是我从博客上摘抄下来的
- 和大家一起分享
- 这个题目用到了线段树的知识 因为用普通的循环 我们得到的时间复杂度为O(m*n) 肯定会超时
- 这个题目比较复杂 我写的也不是很好 大家多看几遍 多理解
- 个人水平 有限 欢迎批评指正~
所谓的线段树如下图:
每个数的结点 里面包含的是线段
比如根结点包含的线段范围为 [a,b]
那么它的左子结点 包含线段的范围为 [a,(a+b)/2] 右子结点包含的线段范围为 [(a+b)/2+1,b]
(a+b)/2 即为 mid, 如此这样一直分支下去 直到每个结点中包含的线段成了一个点 线段树便构建好了
参考代码:
- #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]; //线段树的每个节点 其中包括三个参数 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 ne=now<<1; //将结点的序号*2;
- 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){ //在线段树中寻找对应的区间 给对应该区间的结点加上该发的
- 苹果数,即为在那个结点下的所有的子节点的区间里的小孩均会被发苹果。 (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 ne=now<<1; //结点的序号*2,方便构建新的结点
- 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);
- }
- return 0;
- }
来源: http://www.dotcpp.com/blog/3865.html