https://www.luogu.com.cn/problem/P3373
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,q,Mod,a[N];
int tag_mul[N*4],tag_add[N*4],tree[N*4];
void modify(int l,int r,int now,int mul,int add)
{
tree[now]=tree[now]*mul+(r-l+1)*add;
tree[now]%=Mod;
tag_mul[now]*=mul;
tag_mul[now]%=Mod;
tag_add[now]=tag_add[now]*mul+add;
tag_add[now]%=Mod;
}
void push_down(int l,int r,int now)
{
int mid=(l+r)/2;
modify(1,mid,now*2,tag_mul[now],tag_add[now]);
modify(mid+1,r,now*2+1,tag_mul[now],tag_add[now]);
tag_mul[now]=1;
tag_add[now]=0;
}
void push_up(int now)
{
tree[now]=tree[now*2]+tree[now*2+1];
tree[now]%=Mod;
}
void build(int l,int r,int now)
{
tag_mul[now]=1;
if(l==r)
{
tree[now]=a[l];
return;
}
int mid=(l+r)/2;
build(l,mid,now*2);
build(mid+1,r,now*2+1);
push_up(now);
}
void update_mul(int l,int r,int nl,int nr,int now,int k)//区间乘
{
if(l>=nl&&r<=nr)
{
tag_mul[now]*=k;
tag_mul[now]%=Mod;
tag_add[now]*=k;
tag_add[now]%=Mod;
tree[now]*=k;
tree[now]%=Mod;
return;
}
push_down(l,r,now);
int mid=(l+r)/2;
if(nl<=mid) update_mul(l,mid,nl,nr,now*2,k);
if(nr>mid) update_mul(mid+1,r,nl,nr,now*2+1,k);
push_up(now);
}
void update_add(int l,int r,int nl,int nr,int now,int k)//区间加
{
if(l>=nl&&r<=nr)
{
tag_add[now]+=k;
tag_add[now]%=Mod;
tree[now]+=(r-l+1)*k;
tree[now]%=Mod;
return;
}
push_down(l,r,now);
int mid=(l+r)/2;
if(nl<=mid) update_add(l,mid,nl,nr,now*2,k);
if(nr>mid) update_add(mid+1,r,nl,nr,now*2+1,k);
push_up(now);
}
int query(int l,int r,int nl,int nr,int now)//区间求和
{
int ans=0;
if(l>=nl&&r<=nr) return tree[now];
push_down(l,r,now);
int mid=(l+r)/2;
if(nl<=mid) ans+=query(l,mid,nl,nr,now*2);
if(nr>mid) ans+=query(mid+1,r,nl,nr,now*2+1);
return ans%Mod;
}
signed main()
{
cin>>n>>q>>Mod;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
while(q--)
{
int op,x,y,k;
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
update_mul(1,n,x,y,1,k);
}
if(op==2)
{
cin>>x>>y>>k;
update_add(1,n,x,y,1,k);
}
if(op==3)
{
cin>>x>>y;
cout<<query(1,n,x,y,1)<<"\n";
}
}
return 0;
}