RT

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
using namespace std;
namespace Yorihime_Nao{
    template<class T> T MAX(T x,T y){
        return x>y?x:y;
    }
    template<class T,class ... Arg> T MAX(T x,T y,Arg ... arg){
        return MAX(x>y?x:y,arg...);
    }
    template<class T> T MIN(T x,T y){
        return x<y?x:y;
    }
    template<class T,class ... Arg> T MIN(T x,T y,Arg ... arg){
        return MIN(x<y?x:y,arg...);
    }
    template<class T> T lowbit(T x){
        return x&-x;
    }
}
using namespace Yorihime_Nao;
const ll MAXN=1e5+5;
ll n,p,q,arr[MAXN],op,l,r,x;
ll data[MAXN<<2],lazy_add[MAXN<<2],lazy_mul[MAXN<<2];
void build(ll id,ll L,ll R){
    if(L==R){
        data[id]=arr[L]%p;
        lazy_add[id]=0;
        lazy_mul[id]=1;
        return;
    }
    ll mid=L+R>>1;
    build(id<<1,L,mid);
    build((id<<1)+1,mid+1,R);
    data[id]=(data[id<<1]+data[(id<<1)+1])%p;
    return;
}
void push_down(ll id,ll L,ll R){
    ll mid=L+R>>1;
    data[id<<1]=(data[id<<1]*lazy_mul[id]%p+lazy_add[id]*(mid-L+1)%p)%p;
    lazy_add[id<<1]=(lazy_add[id<<1]*lazy_mul[id]%p+lazy_add[id])%p;
    lazy_mul[id<<1]=lazy_mul[id<<1]*lazy_mul[id]%p;
    data[(id<<1)+1]=(data[(id<<1)+1]*lazy_mul[id]%p+lazy_add[id]*(R-mid)%p)%p;
    lazy_add[(id<<1)+1]=(lazy_add[(id<<1)+1]*lazy_mul[id]%p+lazy_add[id])%p;
    lazy_mul[(id<<1)+1]=lazy_mul[(id<<1)+1]*lazy_mul[id]%p;
    lazy_add[id]=0;
    lazy_mul[id]=1;
    return;
}
void add(ll id,ll L,ll R,ll UL,ll UR,ll delta){
    if(L>UR||R<UL)return;
    if(UL<=L&&R<=UR){
        data[id]=(data[id]+(R-L+1)*delta%p)%p;
        lazy_add[id]=(lazy_add[id]+delta)%p;
        return;
    }
    push_down(id,L,R);
    ll mid=L+R>>1;
    add(id<<1,L,mid,UL,UR,delta);
    add((id<<1)+1,mid+1,R,UL,UR,delta);
    data[id]=(data[id<<1]+data[(id<<1)+1])%p;
    return;
}
void mul(ll id,ll L,ll R,ll UL,ll UR,ll delta){
    if(L>UR||R<UL)return;
    if(UL<=L&&R<=UR){
        data[id]=data[id]*delta%p;
        lazy_add[id]=lazy_mul[id]*delta%p;
        return;
    }
    push_down(id,L,R);
    ll mid=L+R>>1;
    mul(id<<1,L,mid,UL,UR,delta);
    mul((id<<1)+1,mid+1,R,UL,UR,delta);
    data[id]=(data[id<<1]+data[(id<<1)+1])%p;
    return;
}
ll query(ll id,ll L,ll R,ll QL,ll QR){
    if(L>QR||R<QL)return 0;
    if(QL<=L&&R<=QR)return data[id];
    push_down(id,L,R);
    ll mid=L+R>>1;
    return (query(id<<1,L,mid,QL,QR)+query((id<<1)+1,mid+1,R,QL,QR))%p;
}
int main(){
    scanf("%lld%lld",&n,&p);
    for(int i=1;i<=n;i++)scanf("%lld",&arr[i]);
    build(1,1,n);
    scanf("%lld",&q);
    for(int i=1;i<=q;i++){
        scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1){
            scanf("%lld",&x);
            mul(1,1,n,l,r,x);
        }
        if(op==2){
            scanf("%lld",&x);
            add(1,1,n,l,r,x);
        }
        if(op==3)printf("%lld\n",query(1,1,n,l,r));
    }
    return 0;
}

线段树2
写挂了