【线段树】加法、乘法标记加持的线段树

题目链接

#include<bits/stdc++.h>
#define MAXN 100005
#define mid ((l+r)>>1)
using namespace std;

int n,m,mod,flag,x,y,z;
long long a[MAXN];

struct tree
{
    long long v,mul,add;
    //数据，乘法懒标，加法懒标
}t[4*MAXN];

void build(int root,int l,int r)
{
    t[root].add=0;
    t[root].mul=1;//初始化懒标
    if (l==r) t[root].v=a[l];
    else
    {
        build(root<<1,l,mid);
        build(root<<1|1,mid+1,r);
        t[root].v=t[root<<1].v+t[root<<1|1].v;
    }
    t[root].v%=mod;
    return;
}//初始化建树

void pushdown(int root,int l,int r)//标记下放
{
    t[root<<1].v=(t[root<<1].v*t[root].mul+t[root].add*(mid-l+1))%mod;
    t[root<<1|1].v=(t[root<<1|1].v*t[root].mul+t[root].add*(r-mid))%mod;//更新值
    t[root<<1].add=(t[root<<1].add*t[root].mul+t[root].add)%mod;//左儿子的加法标记
    t[root<<1|1].add=(t[root<<1|1].add*t[root].mul+t[root].add)%mod;//右儿子的加法标记
    t[root<<1].mul=(t[root<<1].mul*t[root].mul)%mod;//左儿子的乘法标记
    t[root<<1|1].mul=(t[root<<1|1].mul*t[root].mul)%mod;//右儿子的乘法标记
    t[root].add=0;t[root].mul=1;//清空标记
}

void addition(int root,int now_l,int now_r,int l,int r,long long k)
{
    if(l>now_r||r<now_l) return;//无重叠部分
    if(l<=now_l&&r>=now_r)//部分重叠
    {
        t[root].add=(t[root].add+k)%mod;//修改加法标记
        t[root].v=(t[root].v+k*(now_r-now_l+1))%mod;//修改当前点
        return;
    }
    pushdown(root,now_l,now_r);
    int Mid=(now_l+now_r)>>1;
    addition(root<<1,now_l,Mid,l,r,k);
    addition(root<<1|1,Mid+1,now_r,l,r,k);
    //二分进行加法操作
    t[root].v=(t[root<<1].v+t[root<<1|1].v)%mod;
    return;
}

void multiplication(int root,int now_l,int now_r,int l,int r,long long k)
{
    if(l>now_r||r<now_l) return;//无重叠部分
    if(l<=now_l&&r>=now_r)//部分重叠
    {
        t[root].v=(t[root].v*k)%mod;//修改当前点
        t[root].add=(t[root].add*k)%mod;//修改加法标记
        t[root].mul=(t[root].mul*k)%mod;//修改乘法标记
        return;
    }
    pushdown(root,now_l,now_r);
    int Mid=(now_l+now_r)>>1;
    multiplication(root<<1,now_l,Mid,l,r,k);
    multiplication(root<<1|1,Mid+1,now_r,l,r,k);
    //二分进行乘法操作
    t[root].v=(t[root<<1].v+t[root<<1|1].v)%mod;
    return;
}

long long query(int root,int now_l,int now_r,int l,int r)
{
    if(l>now_r||r<now_l) return 0;//无重叠部分
    if(l<=now_l&&r>=now_r) return t[root].v;//部分重叠
    pushdown(root,now_l,now_r);
    int Mid=(now_l+now_r)>>1;
    return (query(root<<1,now_l,Mid,l,r)+query(root<<1|1,Mid+1,now_r,l,r))%mod;
}

template<class T> inline void read(T &re)
{
    re=0;T sign=1;char tmp;
    while((tmp=getchar())&&(tmp<'0'||tmp>'9')) if(tmp=='-') sign=-1;re=tmp-'0';
    while((tmp=getchar())&&(tmp>='0'&&tmp<='9')) re=re*10+(tmp-'0');re*=sign;
}

int main()
{
    read(n);read(m);read(mod);
    for(register int i=1;i<=n;i++) read(a[i]);
    build(1,1,n);
    for(register int i=1;i<=m;i++)
    {
        read(flag);
        if(flag==1) {read(x);read(y);read(z);multiplication(1,1,n,x,y,z);}
        else if(flag==2){read(x);read(y);read(z);addition(1,1,n,x,y,z);}
        else if(flag==3){read(x);read(y);printf("%lld\n",query(1,1,n,x,y));}
    }
    return 0;
}

【线段树】加法、乘法标记加持的线段树

原文：https://www.cnblogs.com/tqr06/p/10486283.html