正文前提示

---

题目传送门

主要思路

其实，就是在线段树 $1$ 的基础上加上了一个乘法。

具体做法

Step $1$：主函数逻辑

读入 $n$ 个数，建树，接下来 $q$ 次操作，是 $1$ 就将区间做乘法，是 $2$ 就将区间做加法，是 $3$ 就输出区间和。

主要代码：

    LL n,q;
    scanf("%lld%lld%lld",&n,&q,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i]);
    }
    build(1,1,n);//建树
    while(q--){
        int op;
        scanf("%d",&op);
        if(op==1){
            LL x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            update(1,x,y,k,0);//从节点 1 开始，范围是 x ~ y，给每一个数乘 k，给每一个数加 0。
        }else if(op==2){
            LL x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            update(1,x,y,1,k);//从节点 1 开始，范围是 x ~ y，给每一个数乘 1，给每一个数加 k。
        }else{
            LL x,y;
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,x,y));//从节点 1 开始，范围是 x ~ y，查询区间和。
        }
    }

Step $2$：建树

先声明这个节点的范围是 $l\sim r$ 的；其次，把这个节点的 $sum$ 初值置为 $w_l$ 或 $w_r$（你爱写哪个写哪个）；接着，把乘的懒标记赋好 $1$ 的初值，加的懒标记赋好 $0$ 的初值；然后，判断当前是否为叶子结点（$l$ 是不是等于 $r$），如果是，返回，否则递归建立左右子树直到当前节点变成叶子结点为止；最后，把左右ㄦ子的 $sum$ 累加到父亲那里去。

主要代码：

void pushup(LL p){
    tr[p].sum=(tr[lc].sum+tr[rc].sum)%m;//把左右ㄦ子的和都累加过来。
}
void build(LL p,LL l,LL r){
    tr[p]={l,r,w[r],1,0};
    if(l==r)return;
    LL mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(p);
}

Step $3$：update（更新函数）逻辑

首先，如果越界了，赶快返回；其次，如果当前节点范围完全覆盖需要更新的部分，使用 calc 函数更新线段树后立即返回；接着，下传懒标记；然后，更新左右ㄦ子；最后，把左右ㄦ子的 $sum$ 累加到父亲那里去。特别强调！！！更新的范围和节点的范围是不一样的！更新的范围始终保持不变！！！

这里讲一下 calc 函数怎么写。首先，这个函数是用来维护区间和和两个懒标记的。注意：需要先乘后加才能保证精度不丢失，因为先加后乘的话，新的 $t.add$ 就会是 $t.add+\dfrac{add}{mul}$，如果 $\dfrac{add}{mul}$ 不是整数，那么精度将丢失。子节点新的 $t.mul$ 为 $t.mul \times mul$，新的 $t.add$ 为 $t.add\times mul+add$。这里还得计算 $t.sum$。我们推出一个公式来计算它：$\left(x_l\times mul+add\right)+\cdots+\left(x_r\times mul+add\right)$，化简后就是：

$$\begin{align} & \left(x_l\times mul+add\right)+\cdots+\left(x_r\times mul+add\right)\\ = & \left(x_l+\cdots+x_r\right)\times mul+\left(r-l+1\right) \times add\\ = & t.sum\times mul+\left(r-l+1\right) \times add \end{align} $$

主要代码：

void calc(node &t/*一定要传引用，不然无法修改 tr 数组*/,LL mul,LL add){
    t.sum=(t.sum*mul+(t.r-t.l+1)*add)%m;
    t.mul=t.mul*mul%m;      //⎫
//                             先乘后加，否则精度丢失
//                            ⎬新的 mul 为 mul × m，新的 add 为 add × m + a。
    t.add=(t.add*mul+add)%m;//⎭
}
void pushdown(LL p){//下传懒标记
    calc(tr[lc],tr[p].mul,tr[p].add);
    calc(tr[rc],tr[p].mul,tr[p].add);
    tr[p].mul=1;//⎫
//                 清空懒标记
//                ⎬
    tr[p].add=0;//⎭
}
void update(LL p,LL l,LL r,LL mul,LL add){
    if(tr[p].r<l||tr[p].l>r)return;//越界
    if(l<=tr[p].l&&tr[p].r<=r){//完全覆盖
        calc(tr[p],mul,add);
        return;
    }
    pushdown(p);
    update(lc,l,r,mul,add);
    update(rc,l,r,mul,add);
    pushup(p);
}

Step $4$：query 查询函数

首先，如果越界了，赶快返回；接着，如果当前节点范围完全覆盖需要更新的部分，返回当前节点的 $sum$ 值；然后，下传懒标记；最后，返回左ㄦ子的查询结果和右ㄦ子的查询结果的和。

LL query(LL p,LL l,LL r){
    if(tr[p].r<l||tr[p].l>r)return 0;//越界
    if(l<=tr[p].l&&tr[p].r<=r){//完全覆盖
        return tr[p].sum%m;
    }
    pushdown(p);
    return (query(lc,l,r)+query(rc,l,r))%m;
}

AC 代码：

#include<iostream>
#include<stdio.h>
#define LL long long
#define lc p<<1   //左ㄦ子
#define rc p<<1|1 //右ㄦ子
using namespace std;
LL m,w[100005];
struct node{
    LL l,r,sum,mul,add;
}tr[400005];//大小是 w 数组的 4 倍。
void pushup(LL p){
    tr[p].sum=(tr[lc].sum+tr[rc].sum)%m;//把左右ㄦ子的和都累加过来。
}
void calc(node &t/*一定要传引用，不然无法修改 tr 数组*/,LL mul,LL add){
    t.sum=(t.sum*mul+(t.r-t.l+1)*add)%m;
    t.mul=t.mul*mul%m;      //⎫
//                             先乘后加，否则精度丢失
//                            ⎬新的 mul 为 mul × m，新的 add 为 add × m + a。
    t.add=(t.add*mul+add)%m;//⎭
}
void pushdown(LL p){//下传懒标记
    calc(tr[lc],tr[p].mul,tr[p].add);
    calc(tr[rc],tr[p].mul,tr[p].add);
    tr[p].mul=1;//⎫
//                 清空懒标记
//                ⎬
    tr[p].add=0;//⎭
}
void build(LL p,LL l,LL r){
    tr[p]={l,r,w[r],1,0};
    if(l==r)return;
    LL mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(p);
}
void update(LL p,LL l,LL r,LL mul,LL add){
    if(tr[p].r<l||tr[p].l>r)return;//越界
    if(l<=tr[p].l&&tr[p].r<=r){//完全覆盖
        calc(tr[p],mul,add);
        return;
    }
    pushdown(p);
    update(lc,l,r,mul,add);
    update(rc,l,r,mul,add);
    pushup(p);
}
LL query(LL p,LL l,LL r){
    if(tr[p].r<l||tr[p].l>r)return 0;//越界
    if(l<=tr[p].l&&tr[p].r<=r){//完全覆盖
        return tr[p].sum%m;
    }
    pushdown(p);
    return (query(lc,l,r)+query(rc,l,r))%m;
}
int main(){
    LL n,q;
    scanf("%lld%lld%lld",&n,&q,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i]);
    }
    build(1,1,n);//建树
    while(q--){
        int op;
        scanf("%d",&op);
        if(op==1){
            LL x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            update(1,x,y,k,0);//从节点 1 开始，范围是 x ~ y，给每一个数乘 k，给每一个数加 0。
        }else if(op==2){
            LL x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            update(1,x,y,1,k);//从节点 1 开始，范围是 x ~ y，给每一个数乘 1，给每一个数加 k。
        }else{
            LL x,y;
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,x,y));//从节点 1 开始，范围是 x ~ y，查询区间和。
        }
    }
    return 0;
}

正文后闲话

其实，这道题你想用暴力枚举过这道题也没问题，注意超时就行。