浅谈线段树中加与乘标记的下放

假设我们一个节点为[val,mul,add],其中val代表该节点的权值,mul为乘法标记,add为加法标记

那么我们有两种表示方式,

  • 第一种:先加再乘

此时该节点为(val+add)*mul

当再遇到一个[_mul,_add]的标记时,

此时节点为[(val+add)*mul+_add]*_mul

把式子展开并重新化为(val+add')*mul'的形式 (也就是提出mul*_mul这一项)得

(val+add+\frac{\_add}{mul})*mul*\_mul

我们发现这里有个除法,会损失很多精度

因此我们换一个思路

  • 第二种:先乘再加

此时该节点为(val*mul)+add

当再遇到一个[\_mul,\_add]的标记时,

此时节点为[(val*mul)+add]*\_mul+\_add

把式子展开并重新化为(val*mul')+add'的形式

val*mul*\_mul+add*\_mul+\_add

我们发现这样不需要除法,因此我们选用第二种

其实线段树标记的下放一般都是这个套路

放一下丑陋的代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ls k<<1
#define rs k<<1|1
#define int long long 
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N,M,mod;
struct node
{
    int mul,add,sum,l,r,siz;
}T[MAXN];
void update(int k)
{
    T[k].sum=(T[ls].sum%mod+T[rs].sum%mod)%mod;
}
void ps(int x,int f)
{
    T[x].mul=(T[x].mul%mod*T[f].mul%mod)%mod;
    T[x].add=(T[x].add*T[f].mul)%mod;
    T[x].add=(T[x].add+T[f].add)%mod;
    T[x].sum=(T[x].sum%mod*T[f].mul%mod)%mod;
    T[x].sum=(T[x].sum+T[f].add%mod*T[x].siz)%mod;
}
void pushdown(int k)
{
    if(T[k].add==0&&T[k].mul==1) return ;
    ps(ls,k);
    ps(rs,k);
    T[k].add=0;
    T[k].mul=1;
}
void Build(int k,int ll,int rr)
{
    T[k].l=ll;T[k].r=rr;T[k].siz=rr-ll+1;T[k].mul=1;
    if(ll==rr)
    {
        T[k].sum=read()%mod;
        return ;
    }
    int mid=ll+rr>>1;
    Build(ls,ll,mid);
    Build(rs,mid+1,rr);
    update(k);
}
void IntervalMul(int k,int ll,int rr,int val)
{
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        T[k].sum=(T[k].sum*val)%mod;
        T[k].mul=(T[k].mul*val)%mod;
        T[k].add=(T[k].add*val)%mod;
        return ;
    }
    pushdown(k);
    int mid=T[k].l+T[k].r>>1;
    if(ll<=mid) IntervalMul(ls,ll,rr,val);
    if(rr>mid)  IntervalMul(rs,ll,rr,val);
    update(k);
}
void IntervalAdd(int k,int ll,int rr,int val)
{
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        T[k].sum=(T[k].sum+T[k].siz*val)%mod;
        T[k].add=(T[k].add+val)%mod;
        return ;
    }
    pushdown(k);
    int mid=T[k].l+T[k].r>>1;
    if(ll<=mid) IntervalAdd(ls,ll,rr,val);
    if(rr>mid)  IntervalAdd(rs,ll,rr,val);
    update(k);
}
int IntervalSum(int k,int ll,int rr)
{
    int ans=0;
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        ans=(ans+T[k].sum)%mod;
        return ans;
    }
    pushdown(k);
    int mid=T[k].l+T[k].r>>1;
    if(ll<=mid) ans=(ans+IntervalSum(ls,ll,rr))%mod;
    if(rr>mid)  ans=(ans+IntervalSum(rs,ll,rr))%mod;
    return ans%mod;
}
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    N=read();M=read();mod=read();
    Build(1,1,N);
    while(M--)
    {
        int opt=read();
        if(opt==1)
        {
            int l=read(),r=read(),val=read()%mod;
            IntervalMul(1,l,r,val);
        }
        else if(opt==2)
        {
            int l=read(),r=read(),val=read()%mod;
            IntervalAdd(1,l,r,val);
        }
        else if(opt==3)
        {
            int l=read(),r=read();
            printf("%lld\n",IntervalSum(1,l,r)%mod);
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java初学

MD5算法

20240
来自专栏cs

python爬虫知识回顾

最常用的requests库, 通过requests对象的get方法,获取一个response对象。jsp的东西。

13230
来自专栏简书专栏

基于tensorflow+CNN的搜狐新闻文本分类

tensorflow是谷歌google的深度学习框架,tensor中文叫做张量,flow叫做流。 CNN是convolutional neural netwo...

31020
来自专栏AI研习社

如何利用微信监管你的TF训练?

之前回答问题【在机器学习模型的训练期间,大概几十分钟到几小时不等,大家都会在等实验的时候做什么?(http://t.cn/Rl8119m)】的时候,说到可以用微...

37240
来自专栏coolblog.xyz技术专栏

红黑树详细分析,看了都说好

红黑树是一种自平衡的二叉查找树,是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明,在当时被称为对称二叉 B 树(symmetric bin...

881220
来自专栏生信宝典

Bedtools使用简介

75440
来自专栏Python小屋

Python切分图像小案例(1、3、2、4象限子图互换)

首先解释上一篇文章详解Python科学计算扩展库numpy中的矩阵运算(1)最后的习题,该问题答案是10 ** 8 = 100000000,原因在于Python...

43070
来自专栏林欣哲

隐含层权重参数的初始化方式的对比实验

全1或全0初始化 全1或全0初始化的训练效果 ? After 858 Batches (2 Epochs): Validation Accuracy 11...

37570
来自专栏超智能体

YJango:TensorFlow中层API Datasets+TFRecord的数据导入

2. 对接性:TensorFlow中也加入了高级API (Estimator、Experiment,Dataset)帮助建立网络,和Keras等库不一样的是:这...

1K230
来自专栏小小挖掘机

TensorFlow 和 NumPy 的 Broadcasting 机制探秘

在使用Tensorflow的过程中,我们经常遇到数组形状不同的情况,但有时候发现二者还能进行加减乘除的运算,在这背后,其实是Tensorflow的broadca...

13120

扫码关注云+社区

领取腾讯云代金券