題目描述

如題，已知一個(gè)數(shù)列狸棍，你需要進(jìn)行下面兩種操作：
1.將某區(qū)間每一個(gè)數(shù)加上x
2.將某區(qū)間每一個(gè)數(shù)乘上x
3.求出某區(qū)間每一個(gè)數(shù)的和

輸入輸出格式

輸入格式
第一行包含三個(gè)整數(shù)N鉴扫、M赞枕、P，分別表示該數(shù)列數(shù)字的個(gè)數(shù)坪创、操作的總個(gè)數(shù)和模數(shù)炕婶。
第二行包含N個(gè)用空格分隔的整數(shù)，其中第i個(gè)數(shù)字表示數(shù)列第i項(xiàng)的初始值莱预。
接下來(lái)M行每行包含3或4個(gè)整數(shù)柠掂，表示一個(gè)操作，具體如下：
操作1： 格式：1 x y k 含義：將區(qū)間[x,y]內(nèi)每個(gè)數(shù)乘上k
操作2： 格式：2 x y k 含義：將區(qū)間[x,y]內(nèi)每個(gè)數(shù)加上k
操作3： 格式：3 x y 含義：輸出區(qū)間[x,y]內(nèi)每個(gè)數(shù)的和對(duì)P取模所得的結(jié)果
輸出格式
輸出包含若干行整數(shù)锁施，即為所有操作3的結(jié)果陪踩。

輸入輸出樣例

輸入樣例#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

說明

時(shí)空限制：1000ms,128M
數(shù)據(jù)規(guī)模：
對(duì)于30%的數(shù)據(jù)：N<=8杖们，M<=10
對(duì)于70%的數(shù)據(jù)：N<=1000，M<=10000
對(duì)于100%的數(shù)據(jù)：N<=100000肩狂，M<=100000

思路

普通的線段樹模板摘完，只需要再加一個(gè)乘的標(biāo)記就行，但要注意在pushdowm的時(shí)候應(yīng)該先乘后加（你要不嫌麻煩寫一塊兒我也沒意見）傻谁，乘的時(shí)候加法標(biāo)記也要跟著乘

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){
        //區(qū)間加 
        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){
        //區(qū)間乘 
        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;
}