Horbson @ 2022-10-26 13:39:59
找不出哪里出问题了
cmd1是更新,cmd2是查询
在cmd2里面加输出,看到最后根的左右儿子莫名变成了19/1、10/0(区间和/懒标记)
#include<cstdio>
int n,m,value[100001],plus,left,right;
struct node
{
int l,r,sum,add; //左边界 右边界 区间和 懒标记
}tree[400001];
void build(int,int,int);
void cmd1(int);
int cmd2(int);
void spread(int);
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&value[i]);
build(1,n,1);
for(int ct=1,q;ct<=m;ct++)
{
scanf("%d",&q);
if(q==1)
{
scanf("%d%d%d",&left,&right,&plus);
cmd1(1);
}
else if(q==2)
{
scanf("%d%d",&left,&right);
plus = cmd2(1);
printf("%d\n",plus);
}
}
return 0;
}
void build(int l,int r,int num)
{
int mid = (l+r)/2;
tree[num].l = l;
tree[num].r = r;
if(l == r)
{
tree[num].sum = value[l];
return;
}
build(l,mid,num*2);
build(mid+1,r,num*2+1);
tree[num].sum = tree[num*2].sum + tree[num*2+1].sum;
}
void cmd1(int num)
{
if(tree[num].l == tree[num].r)
{
tree[num].sum += plus;
return;
}
if(tree[num].l>=left && tree[num].r<=right)
{
tree[num].sum += plus*(tree[num].r-tree[num].l+1);
tree[num].add += plus;
return;
}
if(tree[num].add) spread(num);
int nl, nr;
for(int kk=0;kk<=1;kk++)
{
nl = tree[num*2+kk].l; nr = tree[num*2+kk].r;
if(nl<=right&&nr>=left)
cmd1(num*2+kk);
}
tree[num].add = 0;
tree[num].sum = tree[num*2].sum + tree[num*2+1].sum;
return;
}
int cmd2(int num)
{
if(tree[num].l>=left && tree[num].r<=right)
return tree[num].sum;
int sum = 0,nl,nr;
spread(num);
for(int kk=0;kk<=1;kk++)
{
nl = tree[num*2+kk].l; nr = tree[num*2+kk].r;
if(nl<=right&&nr>=left)
{
sum += cmd2(num*2+kk);
}
}
return sum;
}
void spread(int num)
{
if(tree[num*2].l != tree[num*2].r)
tree[num*2].add += tree[num].add;
tree[num*2].sum += tree[num].add*(tree[num].r-tree[num].l+1);
if(tree[num*2+1].l != tree[num*2+1].r)
tree[num*2+1].add += tree[num].add;
tree[num*2+1].sum += tree[num].add*(tree[num].r-tree[num].l+1);
tree[num].add = 0;
}
by HBWH_zzz @ 2022-10-26 13:46:40
@Horbson spread
下传标记有误
两个 tree[num*2(+1)].num+=
应该是自己节点的 r-l+1
by HBWH_zzz @ 2022-10-26 13:47:41
if(tree[num*2].l != tree[num*2].r)
tree[num*2].add += tree[num].add;
tree[num*2].sum += tree[num].add*(tree[num*2].r-tree[num*2].l+1);
if(tree[num*2+1].l != tree[num*2+1].r)
tree[num*2+1].add += tree[num].add;
tree[num*2+1].sum += tree[num].add*(tree[num*2+1].r-tree[num*2+1].l+1);
by HBWH_zzz @ 2022-10-26 13:49:01
@Horbson 你的代码还要开 long long
by Horbson @ 2022-10-26 13:52:47
@HBWH_zzz 原来如此,谢谢大佬orz
弄了两个中午终于过了(〜^㉨^)〜
by 155TuT @ 2022-10-26 14:38:06
泪目,线段树模板1和2我写了两天晚自习(3.5h*2)
by Horbson @ 2022-10-28 16:21:46
@155TuT 我们晚自习还得写作业5555
现在因为疫情还封校了,周末还得上课+考第二轮T_T
by 155TuT @ 2022-10-28 18:40:34
@Horbson 我们第二轮取消了5555