#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define M 1000005
struct tree{
int left,right,sum,lazy;
};
tree g[M];
int map[M];
void pushDown(int i)
{
if(g[i].lazy)
{
g[2*i].lazy=1;
g[2*i+1].lazy=1;
g[i].lazy=0;
g[2*i].sum=g[i].sum/(g[i].right-g[i].left+1)*(g[2*i].right-g[2*i].left+1);
g[2*i+1].sum=g[i].sum/(g[i].right-g[i].left+1)*(g[2*i+1].right-g[2*i+1].left+1);
}
}
void buildTree(int left,int right,int i)
{
int mid;
g[i].lazy=0;
g[i].left=left;
g[i].right=right;
if(left==right)
{
g[i].sum=map[left];
return ;
}
mid=(left+right)/2;
buildTree(left,mid,2*i);
buildTree(mid+1,right,2*i+1);
g[i].sum=g[2*i].sum+g[2*i+1].sum;
}
void insert(int l,int r,int num,int i)
{
if(g[i].lazy) pushDown(i);
if(l==g[i].left && g[i].right==r)
{
g[i].sum=(g[i].right-g[i].left+1)*num;
g[i].lazy=1;
return ;
}
int mid=(g[i].left+g[i].right)/2;
if(r<=mid)
insert(l,r,num,2*i);
else if(mid<l)
insert(l,r,num,2*i+1);
else
{
insert(l,mid,num,2*i);
insert(mid+1,r,num,2*i+1);
}
g[i].sum=g[2*i].sum+g[2*i+1].sum;
}
int search(int l,int r,int k)
{
int mid;
if(g[k].lazy) pushDown(k);
if(l==g[k].left && r==g[k].right)
return g[k].sum;
mid=(g[k].left+g[k].right)/2;
if(r<=mid)
search(l,r,2*k);
else if(l>mid)
search(l,r,2*k+1);
else
return search(l,mid,2*k)+search(mid+1,r,2*k+1);
}
int main()
{
int i,m,n,f,l,r,price;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&map[i]);
buildTree(1,n,1);
scanf("%d",&m);
while(m--)
{
scanf("%d",&f);
if(f==1)
{
scanf("%d%d%d",&l,&r,&price);
insert(l,r,price,1);
}
else
{
scanf("%d%d",&l,&r);
printf("%d\n",search(l,r,1));
}
}
}
return 0;
}
[/size]
分享到:
相关推荐
线段树区间更新代码线段树区间更新代码线段树区间更新代码线段树区间更新代码
一种简单的线段树的实现 ,基础功能比较完善
一个讲述线段树的好资料,这里主要是程序部分,希望对广大成员能够有所帮助
浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计...
线段树、线段树啊、线段树,线段树啊、线段树
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的...
线段树点更新
线段树ppt,线段树ppt,线段树ppt,树ppt,线段树ppt,线段树ppt,
线段树(Segment Tree)是一种强大的数据结构,特别适用于处理区间查询和更新问题。本资源不仅提供了线段树的基础模板,还特别包含了线段树乘法操作的实现,进一步扩展了线段树的应用范围。 核心特性: 基础与进阶...
权值线段树和主席树入门PPT,权值线段树,顾名思义就是记录权值的线段树,普通的线段树直接以坐标为l,r建树,而权值线段树是以大小来建树,树上寸的信息是该权值的数量,而通过建树时二分从小到大的性质,可以用这...
讲解线段树基本应用,适合初学者下载使用!
可移植代码,用于单点更新,内有代码移植及运用的详解
ACM学习中 涉及到线段树的代码分析模板
著名的线段树六题 囊括线段树整个知识点, 十分实用 当年凭借此六题, NOIP+NOI秒杀线段树题
线段树完全版,涉及到线段树的所有用法。 包括单点更新(增减,替换),区间求和,区间最值。 区间求最大值的位置。 成段更新(延迟标记,增减)。 离散化 扫描线
本资源是对线段树操作比较完整的操作,包括线段树的动态插入,动态删除和维护,可以查询区段的最大值,最小值,完成线段树的基本操作。
线段树学习ppt
线段树PPT,所有常规用法线段树PPT,所有常规用法线段树PPT,所有常规用法线段树PPT,所有常规用法
线段树,针对一组数的的统计十分方便。 线段树,针对一组数的的统计十分方便。 线段树,针对一组数的的统计十分方便。 线段树,针对一组数的的统计十分方便。 线段树,针对一组数的的统计十分方便。
go语言实现的线段树源码, 可以直接运行, 代码简洁清晰, 快去下载吧