题解 P3373 【【模板】线段树 2】

· · 题解

来篇清新的题解

我感觉楼上各位dalao的代码，些许有些不适合我们这种数据结构萌新

线段树这种简洁而又明了的数据结构，显然还是用数组来存树和tag比较好啊qwq

数组介绍

解法介绍：

我们参考8848的广告

A.根据乘法和加法的优先级不同，所以传tag时，应当两个tag分别传 (两个空间，分别存储，互不干扰)

B.在计算过程中应当随时保持加法tag和乘法tag的相对关系，乘变加也变 （人机分离十米自动报警）

C.较长代码的小技巧：尽量把取值、传值等分支操作加到小函数里，当写pushdown等大函数时直接调用集成，不会出现到处是位运算很杂很乱的情况，显得简洁清新许多，但是不压行会增大常数（很好与优秀只差一点点距离，这段距离，叫码风）

代码解析(已AC)

//相信我，位运算真的会快！！真的不是装B！！
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define il inline
#define Maxn 100100
using namespace std;
ll tr[Maxn<<2],mag[Maxn<<2],aag[Maxn<<2],leaf[Maxn],n,m,md;
ll Q;
ll s,e,z;
ll ans;
ll ls(ll p)
{
    return p<<1;
}//取左儿子
ll rs(ll p)
{
    return p<<1|1;
}//取右儿子
il void pushup(ll p)
{
    tr[p]=(tr[ls(p)]+tr[rs(p)])%md;
}//带模数的向上传值
il void pushup1(ll p)
{
    tr[p]=tr[ls(p)]+tr[rs(p)];
}//建树专用，不带模数的向上传值
void build(ll p,ll l,ll r)
{
    mag[p]=1;
    ll m=(l+r)>>1;
    if(l==r)
    {
        tr[p]=leaf[l];//tr[p]=leaf[r];
        return;
    }
    build(ls(p),l,m);
    build(rs(p),m+1,r);
    pushup1(p);
    tr[p]%=md;
    return;
}//建树，有了取子函数非常简洁qwq
il void pushdown(ll p,ll l,ll r)
{
    ll m=(l+r)>>1;
    tr[ls(p)]=(tr[ls(p)]*mag[p]+aag[p]*(m-l+1))%md;//向左儿子传结果
    tr[rs(p)]=(tr[(rs(p))]*mag[p]+aag[p]*(r-m))%md;//向右儿子传结果
    mag[ls(p)]=(mag[ls(p)]*mag[p])%md;//向左儿子传乘法tag
    mag[rs(p)]=(mag[rs(p)]*mag[p])%md;//向右儿子传乘法tag
    aag[ls(p)]=(aag[ls(p)]*mag[p]+aag[p])%md;//向左儿子传加法tag
    aag[rs(p)]=(aag[rs(p)]*mag[p]+aag[p])%md;//向右儿子传加法tag
    mag[p]=1;
    aag[p]=0;
}//唯一一个略显复杂的函数，向下传tag
il void updmul(ll p,ll l,ll r,ll gl,ll gr,ll k)
{
    if(gr<l||gl>r)return;//若不在此区间就返回上一层，下同
    if(gl<=l&&gr>=r)
    {
        tr[p]=(tr[p]*k)%md;
        mag[p]=(mag[p]*k)%md;
        aag[p]=(aag[p]*k)%md;
        return;
    }
    pushdown(p,l,r);
    ll m=(l+r)>>1;
    updmul(ls(p),l,m,gl,gr,k);
    updmul(rs(p),m+1,r,gl,gr,k);
    pushup(p);
}//常规操作，区间乘法
il void updadd(ll p,ll l,ll r,ll gl,ll gr,ll k)
{
    if(gl>r||gr<l)return;
    if(gl<=l&&gr>=r)
    {
        tr[p]=(tr[p]+(r-l+1)*k)%md;
        aag[p]=(aag[p]+k)%md;
        return;
    }
    pushdown(p,l,r);
    ll m=(l+r)>>1;
    updadd(ls(p),l,m,gl,gr,k);
    updadd(rs(p),m+1,r,gl,gr,k);
    pushup(p);
}//常规操作，区间加法
ll Question(ll p,ll l,ll r,ll gl,ll gr)
{
    if(gl>r||gr<l)return 0;
    if(gl<=l&&gr>=r)
    {
        return tr[p];
    }
    pushdown(p,l,r);
    ll m=(l+r)>>1;
    return (Question(ls(p),l,m,gl,gr)+Question(rs(p),m+1,r,gl,gr))%md;
}//个人喜欢用Question,也可以用query，区间查询
int main()
{
    scanf("%lld%lld%lld",&n,&m,&md);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&leaf[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&Q);
        if(Q==1)
        {
            scanf("%lld%lld%lld",&s,&e,&z);
            updmul(1,1,n,s,e,z);
        }
        if(Q==2)
        {
            scanf("%lld%lld%lld",&s,&e,&z);
            updadd(1,1,n,s,e,z);
        }
        if(Q==3)
        {
            scanf("%lld%lld",&s,&e);
            printf("%lld\n",Question(1,1,n,s,e));
        }
    }
    return ~~(0-0);//(求过)
}

我的这篇题解虽然解法普通，但是我相信这篇题解更容易阅读和理解，所以请管理员欧尼桑们过一下吧qwq（~-△-~）