这题很早之前就做过，当时没理解透，现在理清楚了，感觉很多好东西。
首先，我们需要明确，区间操作加和区间乘，显然要lazytag。
因为是加和乘两种操作，我们去维护两个tag : adtag - 需要下放的加的值 ， mutag - 需要下放的乘的值。
对于区间加这种操作，我们直接去像普通的线段树一样去加上代价即可。
对于区间乘，首先，我们的mutag *= k，然后sum *= k，此时需要注意，我们adtag的值可能还累计的很多没有下放，如果我这里不对adtag操作。
后面下放后，就少去了 * k的代价，所以我们需要让adtag *= k，这样才是正确的需要下放的和代价。
然后主要就是pushdown操作：
首先，
对于左右孩子sum值的更新，首先很显然要加上父亲的adtag（注意要乘上区间长度，因为我们维护的是单个下放代价）。
同时由于我们一直在动态地维护adtag的值，所以我们的mutag 没有必要 * adtag了，就乘上自己即可。
这里也就是题解区一直说的加法优先的概念。
对于左右孩子的mutag ，显然都乘上父亲的mutag 即可。
对于左右孩子的adtag，同理要考虑到累计的adtag的代价，所以要先 *= 父亲的mutag 再去加父亲的adtag。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> pii; const int N = 1e5+5; const int M = 1e6+5; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; LL MD; LL MUL(LL a,LL b){return a * b % MD;} LL ADD(LL a,LL b){return (a + b) % MD;} struct Node{int L,r;LL adtag,mutag,sum;}node[N << 2]; int a[N]; void Pushup(int idx) { node[idx].sum = ADD(node[idx << 1].sum,node[idx << 1 | 1].sum); } void Pushdown(int idx) { int adtag = node[idx].adtag,mutag = node[idx].mutag; int lslen = node[idx << 1].r - node[idx << 1].L + 1; int rslen = node[idx << 1 | 1].r - node[idx << 1 | 1].L + 1; node[idx << 1].sum = ADD(MUL(node[idx << 1].sum,mutag),MUL(lslen,adtag)); node[idx << 1 | 1].sum = ADD(MUL(node[idx << 1 | 1].sum,mutag),MUL(rslen,adtag)); node[idx << 1].adtag = ADD(MUL(node[idx << 1].adtag,mutag),adtag); node[idx << 1].mutag = MUL(node[idx << 1].mutag,mutag); node[idx << 1 | 1].adtag = ADD(MUL(node[idx << 1 | 1].adtag,mutag),adtag); node[idx << 1 | 1].mutag = MUL(node[idx << 1 | 1].mutag,mutag); node[idx].adtag = 0,node[idx].mutag = 1; } void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r; node[idx].adtag = node[idx].sum = 0; node[idx].mutag = 1; if(L == r) { node[idx].sum = a[L] % MD; return ; } int mid = (L + r) >> 1; build(L,mid,idx << 1); build(mid + 1,r,idx << 1 | 1); Pushup(idx); } void tree_mul(int L,int r,int idx,int k) { if(node[idx].L >= L && node[idx].r <= r) { node[idx].sum = MUL(node[idx].sum,k); node[idx].adtag = MUL(node[idx].adtag,k); node[idx].mutag = MUL(node[idx].mutag,k); return ; } int mid = (node[idx].L + node[idx].r) >> 1; Pushdown(idx); if(mid >= L) tree_mul(L,r,idx << 1,k); if(mid < r) tree_mul(L,r,idx << 1 | 1,k); Pushup(idx); } void tree_add(int L,int r,int idx,int k) { if(node[idx].L >= L && node[idx].r <= r) { node[idx].sum = ADD(node[idx].sum,MUL(node[idx].r - node[idx].L + 1,k)); node[idx].adtag = ADD(node[idx].adtag,k); return ; } int mid = (node[idx].L + node[idx].r) >> 1; Pushdown(idx); if(mid >= L) tree_add(L,r,idx << 1,k); if(mid < r) tree_add(L,r,idx << 1 | 1,k); Pushup(idx); } int query(int L,int r,int idx) { if(node[idx].L >= L && node[idx].r <= r) return node[idx].sum; int mid = (node[idx].L + node[idx].r) >> 1,ans = 0; Pushdown(idx); if(mid >= L) ans = ADD(ans,query(L,r,idx << 1)); if(mid < r) ans = ADD(ans,query(L,r,idx << 1 | 1)); return ans; } int main() { int n,m;n = read(),m = read(),MD = read(); for(int i = 1;i <= n;++i) a[i] = read(); build(1,n,1); while(m--) { int op,x,y;op = read(),x = read(),y = read(); if(op == 1) { int k;k = read(); tree_mul(x,y,1,k); } else if(op == 2) { int k;k = read(); tree_add(x,y,1,k); } else printf("%d ",query(x,y,1)); } return 0; }