思路是 成块的维护 小部分遇到乘法直接把每个值都算出来 让后再下加求和 除了乘法之外的地方应该没有问题 因为我已经用他们过了线段树1
#include <cstdio>
#include <cmath>
#include <iostream>
#define ll long long
#define S 5000000
using namespace std;
ll a[S],sum[S],add[S],mod;
int L[S],R[S],pos[S],n,m;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void change(int l,int r,ll d){
int p=pos[l],q=pos[r];
if(p==q){
for(int i=l;i<=r;++i)a[i]+=d,a[i]%=mod;
sum[p]+=(ll)d*(r-l+1)%mod;
sum[p]%=mod;
return;
}
for(int i=p+1;i<=q-1;++i)add[i]+=d,add[i]%=mod;
for(int i=l;i<=R[p];++i)a[i]+=d;
sum[p]+=(ll)(R[p]-l+1)*d%mod;
sum[p]%=mod;
for(int i=L[q];i<=r;++i)a[i]+=d;
sum[q]+=(ll)(r-L[q]+1)*d%mod;
sum[q]%=mod;
}
void change1(int l,int r,int d){
int p=pos[l],q=pos[r];
if(p==q){
for(int i=l;i<=r;++i)a[i]*=d,a[i]%=mod;
sum[p]=0;
for(int i=L[q];i<=R[q];++i)sum[p]+=a[i];sum[p]%=mod;
return;
}
for(int i=p+1;i<=q-1;++i)add[i]*=d,sum[i]*=d,add[i]%=mod,sum[i]%=mod;
for(int i=l;i<=R[p];i++){
a[i]=(a[i]+add[p])*d;
a[i]%=mod;
}
for(int i=L[p];i<l;++i)a[i]+=add[p];
add[p]=0;
sum[p]=0;
for(int i=L[p];i<=R[p];++i)sum[p]+=a[i];
for(int i=L[q];i<=r;++i){
a[i]=(a[i]+add[q])*d;
a[i]%=mod;
}
for(int i=r+1;i<=R[q];++i)a[i]+=add[q];
add[q]=0;
sum[q]=0;
for(int i=L[q];i<=R[q];++i)sum[q]+=a[i];
}
ll ask(int l,int r){
int p=pos[l],q=pos[r];
ll ans=0;
if(p==q){
for(int i=l;i<=r;++i)ans+=a[i];
ans%=mod;
ans+=(ll)add[p]*(r-l+1)%mod;
return ans%mod;
}
for(int i=p+1;i<=q-1;++i)ans+=sum[i]+(ll)add[i]*(R[i]-L[i]+1);
for(int i=l;i<=R[p];++i)ans+=a[i];ans%=mod;
ans+=(ll)add[p]*(R[p]-l+1);ans%=mod;
for(int i=L[q];i<=r;++i)ans+=a[i];ans%=mod;
ans+=(ll)add[q]*(r-L[q]+1);
return ans%mod;
}
int main(){
n=read();m=read();mod=read();
for(int i=1;i<=n;++i)a[i]=read();
int t=sqrt(n);
for(int i=1;i<=t;++i){
L[i]=(i-1)*sqrt(n)+1;
R[i]=i*sqrt(n);
}
if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
for(int i=1;i<=t;++i){
for(int j=L[i];j<=R[i];++j){
pos[j]=i;
sum[i]+=a[j];
}
}
while(m--){
int op;
int l,r,d;
op=read();
if(op==1)l=read(),r=read(),d=read(),change1(l,r,d);
if(op==2)l=read(),r=read(),d=read(),change(l,r,d);
if(op==3)l=read(),r=read(),printf("%lld\n",ask(l,r));
}
}