题目做法其它题解已经阐述的很详细了，这里给出的是线段树指针版写法

#include<cstdio>
#include<iostream>
#define MAXN 200050
#define ll long long
using namespace std; 

ll n, m, p;
ll a[MAXN];

struct node{
    ll l, r, value, lazy1, lazy2;  //lazy1是加法标记，初始化为0;lazy2是乘法标记,初始化为1
    node * left, * right;
    node(){
        l = 0, r = 0, value = 0, lazy1 = 0, lazy2 = 1;
        left = NULL, right = NULL;
    }
}; 

node * build(ll l, ll r){
    if(l == r){
        node * cur = new node();
        cur -> value = a[l];
        cur -> l = l, cur -> r = r;
        return cur;
    }
    ll mid = (l + r) >> 1;
    node * left = build(l, mid), * right = build(mid + 1, r);
    node * cur = new node();
    cur -> l = l, cur -> r = r;
    cur -> left = left, cur -> right = right;
    cur -> value = left -> value + right -> value;
    return cur; 
}

void pushdown(node * cur){
    if(cur -> lazy1 == 0 && cur -> lazy2 == 1)
        return;
    ll mid = (cur -> l + cur -> r) >> 1; 
    cur -> left -> value = (cur -> left -> value * cur -> lazy2 + cur -> lazy1 * (mid - cur -> l + 1)) % p;
    cur -> right -> value = (cur -> right -> value * cur -> lazy2 + cur -> lazy1 * (cur -> r - mid)) % p;
    cur -> left -> lazy2 = (cur -> left -> lazy2 * cur -> lazy2) % p;
    cur -> right -> lazy2 = (cur -> right -> lazy2 * cur -> lazy2) % p;
    cur -> left -> lazy1 = (cur -> left -> lazy1 * cur -> lazy2 + cur -> lazy1) % p;
    cur -> right -> lazy1 = (cur -> right -> lazy1 * cur -> lazy2 + cur -> lazy1) % p;
    cur -> lazy1 = 0, cur -> lazy2 = 1; 
}

ll query(ll l, ll r, node * cur){
    if(cur -> l >= l && cur -> r <= r)
        return cur -> value % p;
    pushdown(cur);
    ll mid = (cur -> l + cur -> r) >> 1;
    if(l > mid) return query(l, r, cur -> right);
    else if(r <= mid) return query(l, r, cur -> left);
    else return (query(l, mid, cur -> left) + query(mid + 1, r, cur -> right)) % p;
}

void add(ll l, ll r, ll d, node * cur){
    if(cur -> l >= l && cur -> r <= r){
        cur -> lazy1 = (cur -> lazy1 + d) % p;
        cur -> value = (cur -> value + d * (r - l + 1)) % p;
    }
    else{
        pushdown(cur);
        ll mid = (cur -> l + cur -> r) >> 1;
        if(l > mid) add(l, r, d, cur -> right);
        else if(r <= mid) add(l, r, d, cur -> left);
        else{
            add(l, mid, d, cur -> left);
            add(mid + 1, r, d, cur -> right);
        }
        cur -> value = (cur -> left -> value + cur -> right -> value) % p;
    }
}

void mul(ll l, ll r, ll m, node * cur){
    if(cur -> l >= l && cur -> r <= r){
        cur -> lazy1 = (cur -> lazy1 * m) % p;
        cur -> lazy2 = (cur -> lazy2 * m) % p;
        cur -> value = (cur -> value * m) % p;
    }
    else{
        pushdown(cur);
        ll mid = (cur -> l + cur -> r) >> 1;
        if(l > mid) mul(l, r, m, cur -> right);
        else if(r <= mid) mul(l, r, m, cur -> left);
        else{
            mul(l, mid, m, cur -> left);
            mul(mid + 1, r, m, cur -> right);
        }    
        cur -> value = (cur -> left -> value + cur -> right -> value) % p;
    }
}

int main(){
    scanf("%lld%lld", &n, &p);
    for(ll i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    node * head = build(1, n);
    scanf("%lld", &m);
    for(ll i = 1; i <= m; i++){
        int opt;
        ll x, y, z;
        scanf("%d", &opt);
        if(opt == 1){
            scanf("%lld%lld%lld", &x, &y, &z);
            mul(x, y, z % p, head);
        }
        else if(opt == 2){
            scanf("%lld%lld%lld", &x, &y, &z);
            add(x, y, z % p, head);
        }
        else{
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", query(x, y, head));
        }
    }
    return 0;
}