【MnZn求助线段树】样例输出11 8 23

P3372 【模板】线段树 1

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


|