题目描述

如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.将某区间每一个数乘上x
3.求出某区间每一个数的和

输入输出格式

输入格式
第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1：格式：1 x y k 含义：将区间[x,y]内每个数乘上k
操作2：格式：2 x y k 含义：将区间[x,y]内每个数加上k
操作3：格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果
输出格式
输出包含若干行整数，即为所有操作3的结果。

输入输出样例

输入样例#1

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

输出样例#1

17
2

说明

时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000

思路

普通的线段树模板，只需要再加一个乘的标记就行，但要注意在pushdowm的时候应该先乘后加~~（你要不嫌麻烦写一块儿我也没意见）~~，乘的时候加法标记也要跟着乘

C++代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rr register
using namespace std;

typedef long long LL;
const int maxn=1e5+10;
int n,m,Q;
int a[maxn];

inline LL read(){//珂朵莉版快读~~ 
    LL chtholly=0,willem=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')willem=-1;c=getchar();}
    while(c<='9' && c>='0'){chtholly=chtholly*10+(LL)(c-'0');c=getchar();}
    return chtholly*willem;
}

struct segment_tree{
#define lson (u<<1)
#define rson (u<<1|1)
    LL sum[maxn<<2],addv[maxn<<2],mul[maxn<<2],p;
    inline void pushup(int u){sum[u]=(sum[lson]+sum[rson])%p;}
    inline void build(int u,int l,int r){
        addv[u]=0,mul[u]=1;
        if(l==r){sum[u]=a[l];return;}
        int mid=(l+r)>>1;
        build(lson,l,mid);build(rson,mid+1,r);
        pushup(u);
    }
    inline void pushdown(int u,int lc,int rc){
        if(mul[u]!=1){
            addv[lson]=(addv[lson]*mul[u])%p;addv[rson]=(addv[rson]*mul[u])%p;
            mul[lson]=(mul[lson]*mul[u])%p;mul[rson]=(mul[rson]*mul[u])%p;
            sum[lson]=(sum[lson]*mul[u])%p;sum[rson]=(sum[rson]*mul[u])%p;
        }
        if(addv[u]!=0){
            addv[lson]=(addv[lson]+addv[u])%p;addv[rson]=(addv[rson]+addv[u])%p;
            sum[lson]=(sum[lson]+addv[u]*lc%p)%p;sum[rson]=(sum[rson]+addv[u]*rc%p)%p;
        }
        addv[u]=0,mul[u]=1;
    }
    inline void update_add(int u,int l,int r,int ql,int qr,int val){
        //区间加 
        if(ql<=l && r<=qr){
            sum[u]=(sum[u]+val*(r-l+1)%p)%p;
            addv[u]=(addv[u]+val)%p;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(u,mid-l+1,r-mid);
        if(ql<=mid) update_add(lson,l,mid,ql,qr,val);
        if(qr>mid) update_add(rson,mid+1,r,ql,qr,val);
        pushup(u);
    }
    inline void update_mul(int u,int l,int r,int ql,int qr,int val){
        //区间乘 
        if(ql<=l && r<=qr){
            mul[u]=mul[u]*val%p;
            sum[u]=sum[u]*val%p;
            addv[u]=addv[u]*val%p;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(u,mid-l+1,r-mid);
        if(ql<=mid) update_mul(lson,l,mid,ql,qr,val);
        if(qr>mid) update_mul(rson,mid+1,r,ql,qr,val);
        pushup(u);
    }
    inline LL query(int u,int l,int r,int ql,int qr){
        if(ql<=l && r<=qr)return sum[u];
        int mid=(l+r)>>1;
        pushdown(u,mid-l+1,r-mid);
        LL ret=0LL;
        if(ql<=mid) ret=(ret+query(lson,l,mid,ql,qr))%p;
        if(qr>mid) ret=(ret+query(rson,mid+1,r,ql,qr))%p;
        return ret%p;
    }
}tr;

int main(){
    n=read(),m=read(),tr.p=read();
    for(rr int i=1;i<=n;++i)a[i]=read();
    tr.build(1,1,n);
    while(m--){
        Q=read();
        int l=read(),r=read();
        if(Q==2){
            int x=read();
            tr.update_add(1,1,n,l,r,x);
        }
        if(Q==1){
            int x=read();
            tr.update_mul(1,1,n,l,r,x);
        }
        if(Q==3){
            LL ans=tr.query(1,1,n,l,r);
            printf("%lld\n",ans);
        }
    }
    return 0;
}