#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int mod;
int qj[maxn];
struct ll{
bool mo;
int k;
};
struct xds{
int left;
int right;
int ans;
deque <ll> lazy;
};
xds tr[4*maxn];
void build(int le,int ri,int x)
{
tr[x].left=le;
tr[x].right=ri;
if(le==ri)
{
tr[x].ans=qj[le]%mod;
return;
}
int mid=(le+ri)/2;
build(le,mid,2*x);
build(mid+1,ri,2*x+1);
tr[x].ans=(tr[2*x].ans+tr[2*x+1].ans)%mod;
return;
}
void jla(int rt,ll k)
{
if(tr[rt].left==tr[rt].right) return;
if(tr[rt].lazy.empty())
{
tr[rt].lazy.push_back(k);
return;
}
ll t=tr[rt].lazy.back();
if(t.mo==k.mo)
{
tr[rt].lazy.pop_back();
if(t.mo==1) t.k=t.k*k.k%mod;
else t.k=(t.k+k.k)%mod;
tr[rt].lazy.push_back(t);
}
else tr[rt].lazy.push_back(k);
}
void pus(int rt)
{
int le=rt*2,ri=rt*2+1;
while(!tr[rt].lazy.empty())
{
ll k=tr[rt].lazy.front();tr[rt].lazy.pop_front();
jla(le,k),jla(ri,k);
if(k.mo==0) tr[le].ans=(tr[le].ans+k.k*(tr[le].right-tr[le].left+1))%mod;
else tr[le].ans=(int)((long long)tr[le].ans*k.k%mod);
if(k.mo==0) tr[ri].ans=(tr[ri].ans+k.k*(tr[ri].right-tr[ri].left+1))%mod;
else tr[ri].ans=(int)((long long)tr[ri].ans*k.k%mod);
}
}
void xg(int x,int y,int k,int rt,bool mo)
{
if(x>y) return;
if(x<=tr[rt].left&&tr[rt].right<=y)
{
ll t;t.k=k,t.mo=mo;
jla(rt,t);
if(mo==0) tr[rt].ans=(tr[rt].ans+k*(tr[rt].right-tr[rt].left+1))%mod;
else tr[rt].ans=(int)((long long)tr[rt].ans*k%mod);
return;
}
pus(rt);
int mid=(tr[rt].left+tr[rt].right)/2;
if(x<=mid)
xg(x,y,k,2*rt,mo);
if(y>mid)
xg(x,y,k,2*rt+1,mo);
tr[rt].ans=tr[2*rt].ans+tr[2*rt+1].ans;
return;
}
int js(int x,int y,int rt)
{
int ans=0;
if(x>y) return 0;
if(x<=tr[rt].left&&tr[rt].right<=y)
{
return tr[rt].ans;
}
pus(rt);
int mid=(tr[rt].left+tr[rt].right)/2;
if(x<=mid)
ans=(ans+js(x,y,2*rt))%mod;
if(y>mid)
ans=(ans+js(x,y,2*rt+1))%mod;
return ans;
}
signed main()
{
int n,m;
scanf("%d%d%d",&n,&m,&mod);
for(int i=1;i<=n;i++)
scanf("%d",&qj[i]);
build(1,n,1);
for(int ii=1;ii<=m;ii++)
{
int cz;
scanf("%d",&cz);
if(cz==1)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
xg(x,y,k,1,1);
}
if(cz==2)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
xg(x,y,k,1,0);
}
if(cz==3)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",js(x,y,1));
}
}
return 0;
}
之前的队列为了优化已经用双向队列缩小了,但是还是MLE,求教