IaLWH @ 2024-08-06 20:28:34
写完后代码太乱看不出问题力(悲
#include<stdio.h>
#define ll long long
struct node{
ll sum,lazy;
int l,r;
}tree[114514<<2];
ll data[114514];
int n,m;
inline void build(int i,int l,int r){
tree[i].l=l;
tree[i].r=r;
if(l==r){
tree[i].sum=data[i];
return;
}
ll mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
tree[i].sum=tree[i<<1].sum+tree[(i<<1)+1].sum;
}
inline void plus(int l,int r,ll c,int L,int R,int i){
//[l,r]+c changing [L,R]node including i index now
if(l<=L&&r>R){
tree[i].sum+=(R-L+1)*c; //屯好所有子节点的数
tree[i].lazy+=c; //懒标记
return;
}
ll mid=L+R>>1;
if(tree[i].lazy&&L!=R){ //懒标记非空且非叶节点
tree[i<<1].sum+=tree[i].lazy*(mid-L+1);//左边加上数
tree[i<<1|1].sum+=tree[i].lazy*(R-mid);//右边加上数
tree[i<<1].lazy+=tree[i].lazy;
tree[i<<1|1].lazy+=tree[i].lazy; //左右传下懒标记
tree[i].lazy=0; //clear lazy mark
}
if(l<=mid)
plus(l,r,c,L,m,i<<1);
if(r>mid)
plus(l,r,c,mid+1,R,i<<1|1);
tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; //merge
}
ll search(int l,int r,int L,int R,int i){
if(l<=L&&r>R)
return tree[i].sum;
ll mid=L+R>>1;
if(tree[i].lazy){
tree[i<<1].sum+=tree[i].lazy*(mid-L+1);
tree[i<<1|1].sum+=tree[i].lazy*(R-mid);//右边加上数
tree[i<<1].lazy+=tree[i].lazy;
tree[i<<1|1].lazy+=tree[i].lazy; //左右传下懒标记
tree[i].lazy=0; //clear lazy mark
}
ll t;
if(l<=mid)
t=search(l,r,L,mid,i<<1);
if(r>mid)
t+=search(l,r,mid+1,R,i<<1|1);
return t;
}
int main(){
char command;
int x,y;
ll k;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%lld",data+i);
build(1,1,n);
for(int i=0;i<m;i++){
command=getchar();
if(command==49){
scanf("%d%d%lld",&x,&y,&k);
plus(x,y,k,1,n,1);
}else{
scanf("%d%d",&x,&y);
printf("%lld\n",search(x,y,1,n,1));
}
}
return 0;
}
by Error_Eric @ 2024-08-06 20:43:10
@IaLWH 首先你存储线段端点和计算线段端点的做法混合写是什么风格,其次
plus(l,r,c,L,m,i<<1);
里面的 m
又是什么东西(
by IaLWH @ 2024-08-06 20:51:15
@Error_Eric 嗯混合写指得具体是什么不太明白
by zhaobingjun2010 @ 2024-08-06 20:52:14
@ IaLWH
inline void build(int i,int l,int r){
tree[i].l=l;
tree[i].r=r;
if(l==r){
tree[i].sum=data[i];//应该是tree[i].sum=data[l].
return;
}
要注意tree线段树存的是区间数据, l 和 r 才是对应数组中的地址(关注一下)
by zhaobingjun2010 @ 2024-08-06 20:52:51
@IaLWH
by IaLWH @ 2024-08-06 20:56:49
@zhaobingjun2010 哦哦好的,谢谢
by zhaobingjun2010 @ 2024-08-06 21:01:03
@IaLWH
建议你单独写一个函数用来打懒标记
要不然太乱了
by Error_Eric @ 2024-08-06 21:56:43
@IaLWH 一般情况下 struct
里面没有存储 l,r
才需要在 plus()
里面动态计算 L,R
。 你看你初始化 tree[i].l
后面有用过吗。
by _lxc__ @ 2024-08-07 09:09:00
这题用一维前缀和会更方便一些吧