题目来源：https://www.luogu.com.cn/problem/P3373
//
题意：对区间[l,r]可以乘法，加法操作，查询和操作。
//
思路：既有乘法又有加法，肯定是要有两个标记。纯加法和纯乘法操作是很简单的，但是既有乘法又有加法涉及到先乘后加和先加后乘的顺序。
//
//
//
所以现在是如何将先加后成也可以转为lazy标记先乘后加也是正确的：
//
//
题解：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9;
vector<int>tree(4*N,0),arr(N,0),add(4*N,0),mul(4*N,1);
int n,q,Mod,op,x,y,k;
int lp(int p){return p<<1;}//2*p
int rp(int p){return p<<1 |1;}//2*p+1
void pushup(int p){
tree[p]=tree[lp(p)]+tree[rp(p)];
tree[p]%=Mod;
}
void tag_mul(int p,int c){
add[p]*=c,add[p]%=Mod;//标记mul的当前节点有add标记，add标记需要*=c。就算没有add标记（=0），*=c，也等于0
mul[p]*=c,mul[p]%=Mod;//mul标记
tree[p]*=c,tree[p]%=Mod;
}
void pushdown(int p,int len){//下传标记(mul,add),先乘后加
if(mul[p]!=1){//mul下传
tag_mul(lp(p),mul[p]);
tag_mul(rp(p),mul[p]);
mul[p]=1;
}
if(add[p]!=0){//add下传
add[lp(p)]+=add[p],add[lp(p)]%=Mod;
add[rp(p)]+=add[p],add[rp(p)]%=Mod;
tree[lp(p)]+=(len-(len>>1))*add[p],tree[lp(p)]%=Mod;//len是p节点的子节点的区间 。lp:(len-(len>>1)) , rp:(len>>1)
tree[rp(p)]+=(len>>1)*add[p],tree[rp(p)]%=Mod;
add[p]=0;
}
}
void build(int s,int t,int p){
if(s==t){
tree[p]=arr[s],tree[p]%=Mod;
return;
}
int m=(s+t)>>1;
build(s,m,lp(p)),build(m+1,t,rp(p));
pushup(p);
}
void update(int l,int r,int c,int s,int t,int p){
if(l<=s && r>=t){
if(op==1){tag_mul(p,c);}//乘法:mul标记
else if(op==2){//加法：add标记
add[p]+=c,add[p]%=Mod;
tree[p]+=(t-s+1)*c,tree[p]%=Mod;
}
return;
}
pushdown(p,t-s+1);//len=t-s+1
int m=(s+t)>>1;
if(l<=m) {update(l,r,c,s,m,lp(p));}
if(r>=m+1) {update(l,r,c,m+1,t,rp(p));}
pushup(p);
}
int getsum(int l,int r,int s,int t,int p){
if(l<=s && r>=t){
return tree[p];
}
pushdown(p,t-s+1);
int m=(s+t)>>1,sum=0;
if(l<=m) {
sum=getsum(l,r,s,m,lp(p));
sum%=Mod;
}
if(r>=m+1) {
sum+=getsum(l,r,m+1,t,rp(p));
sum%=Mod;
}
return sum%Mod;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q>>Mod;
for(int i=1;i<=n;i++) cin>>arr[i];
build(1,n,1);
while(q--){
cin>>op;
if(op==1 || op==2){//[x,y]*k, +k
cin>>x>>y>>k;
update(x,y,k,1,n,1);
}
if(op==3){
cin>>x>>y;//查询[x,y]
cout<<getsum(x,y,1,n,1)<<'\n';
}
}
return 0;
}