RT 线段树，40分TLE，评测记录。

#include<cstdio>
#define int long long
#define mid ((t[id].l+t[id].r)>>1)
#define lc (id<<1)
#define rc (id<<1|1)

using namespace std;

const int N=1e5+5;

struct tree {
    int l,r,v;
    int f_add,f_mul;
}t[N<<2];

int n,m,p,k,a[N];

void PushDown(int id) {
    if(t[id].f_mul!=1) {
        t[lc].v=t[lc].v*t[id].f_mul%p;
        t[rc].v=t[rc].v*t[id].f_mul%p;
        t[lc].f_add=t[lc].f_add*t[id].f_mul%p;
        t[rc].f_add=t[rc].f_add*t[id].f_mul%p;
        t[lc].f_mul=t[lc].f_mul*t[id].f_mul%p;
        t[rc].f_mul=t[rc].f_mul*t[id].f_mul%p;
        t[id].f_mul=1;
    }
    if(t[id].f_add) {
        t[lc].v=(t[lc].v+(t[lc].r-t[lc].l+1)*t[id].f_add)%p;
        t[rc].v=(t[rc].v+(t[rc].r-t[rc].l+1)*t[id].f_add)%p;
        t[lc].f_add=(t[lc].f_add+t[id].f_add)%p;
        t[rc].f_add=(t[rc].f_add+t[id].f_add)%p;
        t[id].f_add=0;
    }
    return ;
}

void Build(int id,int l,int r) {
    t[id].l=l;
    t[id].r=r;
    t[id].f_mul=1;
    if(l==r)
        t[id].v=a[l];
    else {
        Build(lc,l,mid);
        Build(rc,mid+1,r);
        t[id].v=(t[lc].v+t[rc].v)%p;
    }
}

void UpdateMultiple(int id,int l,int r,int k) {
    if(t[id].l==l && t[id].r==r) {
        t[id].v=t[id].v*k%p;
        t[id].f_add=t[id].f_add*k%p;
        t[id].f_mul=t[id].f_mul*k%p;
    } else {
        PushDown(id);
        if(r<=mid)
            UpdateMultiple(lc,l,r,k);
        else if(l>mid)
            UpdateMultiple(rc,l,r,k);
        else {
            UpdateMultiple(lc,l,mid,k);
            UpdateMultiple(rc,mid+1,r,k);
        }
        t[id].v=(t[lc].v+t[rc].v)%p;
    }
    return ;
}

void UpdateAdd(int id,int l,int r,int k) {
    if(t[id].l==l && t[id].r==r) {
        t[id].v=(t[id].v+(t[id].r-t[id].l+1)*k)%p;
        t[id].f_add=(t[id].f_add+k)%p;
    } else {
        PushDown(id);
        if(r<=mid)
            UpdateAdd(lc,l,r,k);
        else if(l>mid)
            UpdateAdd(rc,l,r,k);
        else {
            UpdateAdd(lc,l,mid,k);
            UpdateAdd(rc,mid+1,r,k);
        }
        t[id].v=(t[lc].v+t[rc].v)%p;
    }
    return ;
}

int Query(int id,int l,int r) {
    if(t[id].l==t[id].r)
        return t[id].v;
    else {
        PushDown(id);
        if(r<=mid)
            return Query(lc,l,r);
        else if(l>mid)
            return Query(rc,l,r);
        else
            return (Query(lc,l,mid)+Query(rc,mid+1,r))%p;
    }
}

signed main() {
    scanf("%lld%lld",&n,&p);
    for(int i=1;i<=n;++i) {
        scanf("%lld",&a[i]);
        a[i]%=p;
    }
    scanf("%lld",&m);
    Build(1,1,n);
    while(m--) {
        int op,x,y;
        scanf("%lld",&op);
        if(op==1) {
            scanf("%lld%lld%lld",&x,&y,&k);
            k%=p;
            UpdateMultiple(1,x,y,k);
        } else if(op==2) {
            scanf("%lld%lld%lld",&x,&y,&k);
            k%=p;
            UpdateAdd(1,x,y,k);
        } else {
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",Query(1,x,y)%p);
        }
    }
    return 0;
}