题解 P3373 【【模板】线段树 2】
来一发分块
关于分块的标记可以参考线段树的，其实差不多
主要的分块姿势都在blog里
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500000;
int n,m,num,mod,q,belong[maxn],block,l[maxn],r[maxn];
LL a[maxn],add[maxn],mul[maxn],d[maxn],x,com,y,z;
char s[10];
LL inline read()
{
LL 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 debug()
//{
// for (int i=1;i<=n;i++)
// printf("%lld ",a[i]+add[belong[i]]);
// puts("");
// for (int i=1;i<=num;i++,puts(""))
// printf("Bolck%lld: l:%lld r:%lld sum:%lld",i,l[i],r[i],d[i]+add[i]*block);
//}
void build()
{
block=sqrt(n);
num=n/block;if (n%block) num++;
for (int i=1;i<=num;i++)
l[i]=(i-1)*block+1,r[i]=i*block,mul[i]=1;
for (int i=1;i<=n;i++)
belong[i]=(i-1)/block+1;
for (int i=1;i<=n;i++)
d[belong[i]]+=a[i];
}
void update_add(int L,int R,LL x)
{
int bl=belong[L],br=belong[R];
if (bl==br)
{
if (add[bl]||mul[bl]!=1)
{
for (int i=l[bl];i<=r[bl];i++)
a[i]=(a[i]*mul[bl]+add[bl])%mod;
d[bl]=(d[bl]*mul[bl]+add[bl]*block)%mod;
add[bl]=0,mul[bl]=1;
}
for (int i=L;i<=R;i++)
a[i]+=x;
d[bl]=(d[bl]+(R-L+1)*x)%mod;
return;
}
if (add[bl]||mul[bl]!=1)
{
for (int i=l[bl];i<=r[bl];i++)
a[i]=(a[i]*mul[bl]+add[bl])%mod;
d[bl]=(d[bl]*mul[bl]+add[bl]*block)%mod;
add[bl]=0,mul[bl]=1;
}
for (int i=L;i<=r[bl];i++)
a[i]=(a[i]+x)%mod;
d[bl]=(d[bl]+(r[bl]-L+1)*x)%mod;
if (add[br]||mul[br]!=1)
{
for (int i=l[br];i<=r[br];i++)
a[i]=(a[i]*mul[br]+add[br])%mod;
d[br]=(d[br]*mul[br]+add[br]*block)%mod;
add[br]=0,mul[br]=1;
}
for (int i=l[br];i<=R;i++)
a[i]=(a[i]+x)%mod;
d[br]=(d[br]+(R-l[br]+1)*x)%mod;
for (int i=bl+1;i<br;i++)
add[i]=(add[i]+x)%mod;
}
void update_mul(int L,int R,LL x)
{
int bl=belong[L],br=belong[R];
if (bl==br)
{
if (add[bl]||mul[bl]!=1)
{
for (int i=l[bl];i<=r[bl];i++)
a[i]=(a[i]*mul[bl]+add[bl])%mod;
d[bl]=(d[bl]*mul[bl]+add[bl]*block)%mod;
add[bl]=0,mul[bl]=1;
}
int more=0;
for (int i=L;i<=R;i++)
more=(more+a[i]*(x-1))%mod,a[i]=(a[i]*x)%mod;
d[bl]=(d[bl]+more)%mod;
return;
}
if (add[bl]||mul[bl]!=1)
{
for (int i=l[bl];i<=r[bl];i++)
a[i]=(a[i]*mul[bl]+add[bl])%mod;
d[bl]=(d[bl]*mul[bl]+add[bl]*block)%mod;
add[bl]=0,mul[bl]=1;
}
int more=0;
for (int i=L;i<=r[bl];i++)
more=(more+a[i]*(x-1))%mod,a[i]=(a[i]*x)%mod;
d[bl]=(d[bl]+more)%mod;
if (add[br]||mul[br]!=1)
{
for (int i=l[br];i<=r[br];i++)
a[i]=(a[i]*mul[br]+add[br])%mod;
d[br]=(d[br]*mul[br]+add[br]*block)%mod;
add[br]=0,mul[br]=1;
}
more=0;
for (int i=l[br];i<=R;i++)
more=(more+a[i]*(x-1))%mod,a[i]=(a[i]*x)%mod;
d[br]=(d[br]+more)%mod;
for (int i=bl+1;i<br;i++)
mul[i]=(mul[i]*x)%mod,
add[i]=(add[i]*x)%mod;
}
void query(int L,int R)
{
LL ans=0;
int bl=belong[L],br=belong[R];
if (bl==br)
{
for (int i=L;i<=R;i++)
ans=(ans+a[i])%mod;
printf("%d\n",(ans*mul[bl]+(R-L+1)*add[bl])%mod);
return;
}
for (int i=L;i<=r[bl];i++)
ans=(ans+a[i])%mod;
ans=(ans*mul[bl]+(r[bl]-L+1)*add[bl])%mod;
int temp=0;
for (int i=l[br];i<=R;i++)
temp=(temp+a[i])%mod;
temp=(temp*mul[br]+(R-l[br]+1)*add[br])%mod;
ans=(ans+temp)%mod;
for (int i=bl+1;i<br;i++)
ans=(ans+d[i]*mul[i]+add[i]*block)%mod;
printf("%lld\n",ans);
}
int main()
{
n=read(),q=read(),mod=read();
for (int i=1;i<=n;i++)
a[i]=read();
build();
for (int i=1;i<=q;i++)
{
com=read(),x=read(),y=read();
if (com==3)
query(x,y);
else
if (com==1)
z=read(),update_mul(x,y,z);
else
z=read(),update_add(x,y,z);
}
}