Description
如题，已知一个数列，你需要进行下面三种操作：
1.将某区间每一个数乘上(x)
2.将某区间每一个数加上(x)
3.求出某区间每一个数的和
Input
第一行包含三个整数(N)、(M)、(P)，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含(N)个用空格分隔的整数，其中第(i)个数字表示数列第i项的初始值。
接下来(M)行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：(1 x y k) 含义：将区间([x,y])内每个数乘上(k)
操作2： 格式：(2 x y k) 含义：将区间([x,y])内每个数加上(k)
操作3： 格式：(3 x y) 含义：输出区间([x,y])内每个数的和对(P)取模所得的结果
Output
输出包含若干行整数，即为所有操作3的结果。
Solution
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100000;
long long sum[4*N+10],multag[4*N+10],addtag[4*N+10],a[N+10];
int n,m,Mod,opt,x,y,k;
inline long long read()
{
long long ans=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
ans=ans*10+ch-'0';
ch=getchar();
}
return ans*f;
}
long long mo(long long x,long long y)
{
return x+y>=Mod?x+y-Mod:x+y;
}
void pushdown(int p,int l,int r)
{
int mid=(l+r)>>1;
if (multag[p]!=1)
{
sum[p<<1]=sum[p<<1]*multag[p]%Mod;
sum[p<<1|1]=sum[p<<1|1]*multag[p]%Mod;
multag[p<<1]=multag[p<<1]*multag[p]%Mod;
multag[p<<1|1]=multag[p<<1|1]*multag[p]%Mod;
addtag[p<<1]=addtag[p<<1]*multag[p]%Mod;
addtag[p<<1|1]=addtag[p<<1|1]*multag[p]%Mod;
multag[p]=1;
}
if (addtag[p])
{
sum[p<<1]=mo(sum[p<<1],addtag[p]*(mid-l+1)%Mod);
sum[p<<1|1]=mo(sum[p<<1|1],addtag[p]*(r-mid)%Mod);
addtag[p<<1]=mo(addtag[p<<1],addtag[p]);
addtag[p<<1|1]=mo(addtag[p<<1|1],addtag[p]);
addtag[p]=0;
}
}
void build(int p,int l,int r)
{
if (l==r)
{
sum[p]=a[l];
multag[p]=1,addtag[p]=0;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
sum[p]=mo(sum[p<<1],sum[p<<1|1]);
multag[p]=1;addtag[p]=0;
}
void modify_mul(int p,int l,int r,int i,int j,long long v)
{
if (l==i && r==j)
{
sum[p]=sum[p]*v%Mod;
multag[p]=multag[p]*v%Mod;
addtag[p]=addtag[p]*v%Mod;
return;
}
pushdown(p,l,r);
int mid=(l+r)>>1;
if (j<=mid) modify_mul(p<<1,l,mid,i,j,v);
else if (i>mid) modify_mul(p<<1|1,mid+1,r,i,j,v);
else
{
modify_mul(p<<1,l,mid,i,mid,v);
modify_mul(p<<1|1,mid+1,r,mid+1,j,v);
}
sum[p]=mo(sum[p<<1],sum[p<<1|1]);
}
void modify_add(int p,int l,int r,int i,int j,long long v)
{
if (l==i && r==j)
{
sum[p]=mo(sum[p],v*(r-l+1)%Mod);
addtag[p]=mo(addtag[p],v);
return;
}
pushdown(p,l,r);
int mid=(l+r)>>1;
if (j<=mid) modify_add(p<<1,l,mid,i,j,v);
else if (i>mid) modify_add(p<<1|1,mid+1,r,i,j,v);
else
{
modify_add(p<<1,l,mid,i,mid,v);
modify_add(p<<1|1,mid+1,r,mid+1,j,v);
}
sum[p]=mo(sum[p<<1],sum[p<<1|1]);
}
long long query(int p,int l,int r,int i,int j)
{
if (l==i && r==j) return sum[p];
pushdown(p,l,r);
int mid=(l+r)>>1;
if (j<=mid) return query(p<<1,l,mid,i,j);
else if (i>mid) return query(p<<1|1,mid+1,r,i,j);
else
{
return mo(query(p<<1,l,mid,i,mid),query(p<<1|1,mid+1,r,mid+1,j));
}
}
int main()
{
n=read(),m=read(),Mod=read();
for (int i=1;i<=n;i++) a[i]=read(),a[i]%=Mod;
build(1,1,n);
while (m--)
{
opt=read();
if (opt==1)
{
x=read(),y=read(),k=read();
k%=Mod;
modify_mul(1,1,n,x,y,k);
}
if (opt==2)
{
x=read(),y=read(),k=read();
k%=Mod;
modify_add(1,1,n,x,y,k);
}
if (opt==3)
{
x=read(),y=read();
printf("%lld
",query(1,1,n,x,y));
}
}
return 0;
}