线段树模板2

#include<bits/stdc++.h>
using namespace std;
#define N 100005     // 定义数组最大长度
#define lc p<<1       // 左孩子节点索引（位运算优化）
#define rc p<<1|1     // 右孩子节点索引（位运算优化）
#define LL long long  // 定义长整型别名

struct tree{
    int l,r;         // 节点表示的区间[l,r]
    int add,mul;     // 加法懒标记、乘法懒标记
    int sum;         // 区间和（已取模）
}t[4*N];             // 线段树数组（开4倍空间）

int n,q,m,a[N],op,x,y,k; // 输入参数：n元素数，q操作数，m模数，a原始数组

// 上推更新父节点区间和
void pushup(int p) {
    t[p].sum = (t[lc].sum + t[rc].sum) % m; // 合并左右子树的和
}

// 下传懒标记（核心操作）
void pushdown(int p){
    if(t[p].mul != 1 || t[p].add) { // 存在待处理的乘/加标记
        int l_len = t[lc].r - t[lc].l + 1; // 左子树区间长度
        int r_len = t[rc].r - t[rc].l + 1; // 右子树区间长度
        
        // 处理左子树：先乘后加
        t[lc].sum = (1ll*t[lc].sum*t[p].mul%m + 1ll*t[p].add*l_len%m) % m;
        t[lc].mul = 1ll*t[lc].mul*t[p].mul%m; // 乘法标记叠加
        t[lc].add = (1ll*t[lc].add*t[p].mul%m + t[p].add) % m; // 加法标记叠加
        
        // 处理右子树：先乘后加
        t[rc].sum = (1ll*t[rc].sum*t[p].mul%m + 1ll*t[p].add*r_len%m) % m;
        t[rc].mul = 1ll*t[rc].mul*t[p].mul%m;
        t[rc].add = (1ll*t[rc].add*t[p].mul%m + t[p].add) % m;
        
        // 清空当前节点标记
        t[p].mul = 1;
        t[p].add = 0;
    }
}

// 构建线段树
void build(int p, int l, int r){
    t[p] = {l, r, 0, 1, 0}; // 初始化：add=0, mul=1, sum=0
    if(l == r) { // 叶子节点
        t[p].sum = a[l] % m; // 直接赋数组值（已取模）
        return;
    }
    int mid = l + r >> 1; // 区间中点
    build(lc, l, mid);    // 递归构建左子树
    build(rc, mid+1, r);  // 递归构建右子树
    pushup(p);            // 合并子节点信息
}

// 区间更新操作（op=1乘法，op=2加法）
void update(int p, int op, int x, int y, int k){
    if(x <= t[p].l && t[p].r <= y) { // 完全覆盖当前区间
        if(op == 1) { // 乘法操作
            t[p].sum = 1ll*t[p].sum*k % m; // 更新区间和
            t[p].mul = 1ll*t[p].mul*k % m; // 乘法标记叠加
            t[p].add = 1ll*t[p].add*k % m; // 加法标记需同步乘（保持先乘后加顺序）
        } else {      // 加法操作
            t[p].sum = (t[p].sum + 1ll*k*(t[p].r-t[p].l+1)) % m; // 更新区间和
            t[p].add = (t[p].add + k) % m; // 加法标记叠加
        }
        return;
    }
    pushdown(p); // 下传当前节点的标记
    int mid = t[p].l + t[p].r >> 1;
    if(x <= mid) update(lc, op, x, y, k);
    if(mid < y) update(rc, op, x, y, k);
    pushup(p); // 上推更新父节点
}

// 区间查询操作
int query(int p, int x, int y){
    if(x <= t[p].l && t[p].r <= y) return t[p].sum % m;
    pushdown(p); // 下传标记确保子节点数据最新
    int res = 0, mid = t[p].l + t[p].r >> 1;
    if(x <= mid) res = (res + query(lc, x, y)) % m;
    if(mid < y) res = (res + query(rc, x, y)) % m;
    return res;
}

int main() {
    scanf("%d%d%d", &n, &q, &m);
    for(int i=1; i<=n; i++) scanf("%d", a+i), a[i] %= m; // 输入时即取模
    build(1, 1, n); // 构建线段树
    while(q--) {
        scanf("%d%d%d", &op, &x, &y);
        if(op == 3) printf("%d\n", query(1, x, y)); // 查询操作
        else {
            scanf("%d", &k);
            update(1, op, x, y, k%m); // 更新操作（k取模）
        }
    }
    return 0;
}