algorithm - 具有惰性传播的线段树 - 将范围内的所有值相乘

Question

我有以下代码，我可以设法编写具有惰性传播的线段树。此代码不适用于将一个范围内的所有数字与一个值相乘，比如 x。我认为我在 update_mult 函数中做错了什么。树维护范围的总和。

我无法找出 update_mult 的问题。高手，能帮我看看我的实现哪里出了问题吗？

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <set>
#include <assert.h>
#include <cstring>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <time.h>
#include <climits>

using namespace std;

#define FOR(i,a,b) for(int i=a;i<b;++i)
#define FORR(i,a,b) for(int i=a;i>=b;--i)
#define FORC(it,container) for(typeof(container.begin()) it=container.begin();it!=container.end();++it)
#define INT(x) scanf("%d",&x)
#define LLD(x) scanf("%lld",&x)
#define STR(x) scanf("%s",x)
#define CHAR(x) scanf("%c",&x)
#define PINT(x) printf("%d\n",x)
#define PLLD(x) printf("%lld\n",x)
#define CLR(x) memset(x,0,sizeof(x));

const int INF = INT_MAX;
const int MAX = 1000001;


typedef long long LL;

LL arr[MAX+5];
LL MOD = 1e9 + 7;

struct data
{
    LL sumsq;
    LL sum;
    LL lazyset;
    LL setval;
    LL lazyMult;
    LL lazyVal;
    LL addval;

    void assignleaf()
    {

    }
    void assignleaf(int idx ,int val)
    {

    }

    void combine(data &l, data &r)
    {
        sum = (l.sum + r.sum)%MOD;
    }
};

data tree[10*MAX+5];

void pushdown(int node,int segs,int sege)
{
    int mid = segs+sege; mid /= 2;

    if(tree[node].lazyset==1)
    {
            tree[node].lazyset=0;

            tree[2*node].lazyset=1;
            tree[2*node+1].lazyset=1;

            tree[2*node].setval = tree[node].setval; 
            tree[2*node+1].setval = tree[node].setval;

            tree[2*node].sum = ((mid-segs+1)*tree[node].setval)%MOD;
            tree[2*node+1].sum = ((sege-mid)*tree[node].setval)%MOD;

            tree[2*node].addval=0;
            tree[2*node+1].addval=0;

    }

    if(tree[node].lazyMult==1)
    {
            tree[node].lazyMult=0;

            tree[2*node].lazyMult=1;
            tree[2*node+1].lazyMult=1;


            tree[2*node].sum = (tree[2*node].sum  * tree[node].lazyVal)%MOD;
            tree[2*node+1].sum = (tree[2*node+1].sum  * tree[node].lazyVal)%MOD;

            tree[2*node].addval=0;
            tree[2*node+1].addval=0;
    }

    if(tree[node].addval)
    {

            tree[2*node].addval = (tree[2*node].addval +tree[node].addval)%MOD;
            tree[2*node+1].addval = (tree[2*node+1].addval +tree[node].addval)%MOD; 

            tree[2*node].sum = (tree[2*node].sum + ((mid-segs+1)*tree[node].addval)%MOD)%MOD;
            tree[2*node+1].sum =(tree[2*node+1].sum+ ((sege-mid)*tree[node].addval)%MOD)%MOD;

            tree[node].addval = 0;
    }   
}

void build_tree(int node,int s,int e)
{
    tree[node].addval=0;
    tree[node].lazyset=0;

    if(s>e) return;

    if(s==e)
    {
        tree[node].sum = arr[s];
        return;
    }

    int mid=(s+e)/2;

    build_tree(2*node,s,mid);
    build_tree(2*node+1,mid+1,e);

    tree[node].combine(tree[2*node],tree[2*node+1]);

}

LL query(int node,int segs,int sege,int qs,int qe)
{

//cout<<" q -- node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe =  "<<qe<<endl;


    if(segs>sege || segs>qe || sege < qs) 
    {
        if(tree[node].lazyset||tree[node].addval)
             pushdown(node,segs,sege);

        return 0;

    }

    if(tree[node].lazyset || tree[node].addval)
        pushdown(node,segs,sege);

    if(segs>=qs && sege<=qe)
    {

    //cout<<"q1 node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" sumsq  = "<<tree[node].sumsq<<endl;
        return tree[node].sum % MOD;

    }

    int mid= segs+sege; mid /= 2;


    return (query(2*node,segs,mid,qs,qe) + query(2*node+1,mid+1,sege,qs,qe))%MOD;

}

//comm=1
void update_add(int node,int segs,int sege,int qs,int qe,int x)
{

    if(segs>sege||segs>qe||sege<qs) return;

    if(segs>=qs && sege<=qe)
    {
        tree[node].addval = (tree[node].addval+x)%MOD;
        tree[node].sum   = (tree[node].sum + ((LL)(sege-segs+1)*x)%MOD)%MOD;
        return;
    }

    int mid= segs+sege; mid /= 2;

    if(tree[node].lazyset || tree[node].addval)
        pushdown(node,segs,sege);

    update_add(2*node,segs,mid,qs,qe,x);
        update_add(2*node+1,mid+1,sege,qs,qe,x);

    tree[node].combine(tree[2*node],tree[2*node+1]); 


}

void update_mult(int node,int segs,int sege,int qs,int qe,LL x)
{

//cout<<" ua -  node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe =  "<<qe<<" x = "<<x<<endl;


    if(segs>sege||segs>qe||sege<qs) return;

    if(segs>=qs && sege<=qe)
    {
        //tree[node].addval = (tree[node].addval * x)%MOD;
        tree[node].sum   = (tree[node].sum * x)%MOD;
        tree[node].lazyMult = 1;
        tree[node].lazyVal = x;
        tree[node].addval = 0;
        return;
    }

    int mid= segs+sege; mid /= 2;

    if(tree[node].lazyMult || tree[node].addval)
        pushdown(node,segs,sege);

    update_mult(2*node,segs,mid,qs,qe,x);
        update_mult(2*node+1,mid+1,sege,qs,qe,x);

    tree[node].combine(tree[2*node],tree[2*node+1]); 


}

//comm=0
void update_set(int node,int segs,int sege,int qs,int qe,LL x)
{

    //cout<<" node = "<<node<<" segs = "<<segs<<" sege = "<<sege<<" qs = "<<qs<<" qe =  "<<qe<<" x = "<<x<<endl;

    if(segs>sege||segs>qe||sege<qs)
        return;


    if(segs>=qs && sege<=qe)
    {
        tree[node].lazyset= 1;
        tree[node].setval=x;
        tree[node].sum   = ((LL)(sege-segs+1)*x)%MOD;
        tree[node].addval = 0;
        return;
    }

    if(tree[node].lazyset || tree[node].addval)
        pushdown(node,segs,sege);


      int mid= segs+sege; 
      mid /= 2;


     update_set(2*node,segs,mid,qs,qe,x);
     update_set(2*node+1,mid+1,sege,qs,qe,x);

    tree[node].combine(tree[2*node],tree[2*node+1]);


}





int main()
{

    int test = 1;

    FOR(tt,1,test+1)
    {
        int n,q; INT(n); INT(q);


        CLR(arr);
        CLR(tree);

        FOR(i,0,n)
            LLD(arr[i]);

        build_tree(1,0,n-1);

        while(q--)
        {
            int comm; int l,r; 

            INT(comm); INT(l); INT(r);


            if(comm==3)
            {
                //set x 
                LL x; LLD(x);       
                update_set(1,0,n-1,l-1,r-1,x);      

            }
            else if(comm==1)
            {
                //add x
                LL x; LLD(x);               
                update_add(1,0,n-1,l-1,r-1,x);

            }
            else if(comm==2)
            {
                //add x
                LL x; LLD(x);               
                update_mult(1,0,n-1,l-1,r-1,x);

            }
            else if(comm==4)
            {
                LL ans = query(1,0,n-1,l-1,r-1);

                PLLD(ans);

            }

        }

    }

return 0;
}

Answer 1

我认为问题在于下推函数中代码块的顺序。