题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.将某区间每一个数乘上x
3.求出某区间每一个数的和
输入输出格式
输入格式：
第一行包含三个整数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取模所得的结果
输出格式：
输出包含若干行整数，即为所有操作3的结果。
输入输出样例
输入样例#1：
5 5 38 1 5 4 2 3 2 1 4 1 3 2 5 1 2 4 2 2 3 5 5 3 1 4
输出样例#1：
17 2
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^）
样例说明：
故输出应为17、2（40 mod 38=2）
#include<cstdio> #include<cmath> #include<iostream> using namespace std; typedef long long ll; inline ll 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; } const int F=1001; int n,m,q; ll ans,ls,mod,sum[F],tagc[F],tagj[F],b[F][F]; int main(){ n=read();q=read();mod=read(); int m=sqrt(n)+1; for(int i=0;i<n;i++) b[i/m][i%m]=read(); for(int i=0;i<m;i++){ tagc[i]=1; for(int j=0;j<m;j++){ sum[i]+=b[i][j]; } } for(int opt,x,y,z,b1,b2,p1,p2;q--;){ opt=read(); if(opt==1){ x=read()-1;y=read()-1;z=read(); b1=x/m;b2=y/m; p1=x%m;p2=y%m; if(b1==b2){ for(int i=0;i<m;i++){ ls=b[b1][i]; b[b1][i]=(b[b1][i]*tagc[b1]+tagj[b1])%mod; sum[b1]=(sum[b1]+b[b1][i]-ls+mod)%mod; } for(int i=p1;i<=p2;i++){ ls=b[b1][i]; b[b1][i]=(b[b1][i]*z)%mod; sum[b1]=(sum[b1]+b[b1][i]-ls+mod)%mod; } tagc[b1]=1;tagj[b1]=0; } else{ for(int i=0;i<m;i++){ ls=b[b1][i]; b[b1][i]=(b[b1][i]*tagc[b1]+tagj[b1])%mod; sum[b1]=(sum[b1]+b[b1][i]-ls+mod)%mod; } for(int i=p1;i<m;i++){ ls=b[b1][i]; b[b1][i]=(b[b1][i]*z)%mod; sum[b1]=(sum[b1]+b[b1][i]-ls+mod)%mod; } tagc[b1]=1;tagj[b1]=0; for(int i=b1+1;i<b2;i++){ tagc[i]=tagc[i]*z%mod; tagj[i]=tagj[i]*z%mod; } for(int i=0;i<m;i++){ ls=b[b2][i]; b[b2][i]=(b[b2][i]*tagc[b2]+tagj[b2])%mod; sum[b2]=(sum[b2]+b[b2][i]-ls+mod)%mod; } for(int i=0;i<=p2;i++){ ls=b[b2][i]; b[b2][i]=(b[b2][i]*z)%mod; sum[b2]=(sum[b2]+b[b2][i]-ls+mod)%mod; } tagc[b2]=1;tagj[b2]=0; } } else if(opt==2){ x=read()-1;y=read()-1;z=read(); b1=x/m;b2=y/m; p1=x%m;p2=y%m; if(b1==b2){ for(int i=0;i<m;i++){ ls=b[b1][i]; b[b1][i]=(b[b1][i]*tagc[b1]+tagj[b1])%mod; sum[b1]=(sum[b1]+b[b1][i]-ls+mod)%mod; } for(int i=p1;i<=p2;i++){ ls=b[b1][i]; b[b1][i]=(b[b1][i]+z)%mod; sum[b1]=(sum[b1]+b[b1][i]-ls+mod)%mod; } tagc[b1]=1;tagj[b1]=0; } else{ for(int i=0;i<m;i++){ ls=b[b1][i]; b[b1][i]=(b[b1][i]*tagc[b1]+tagj[b1])%mod; sum[b1]=(sum[b1]+b[b1][i]-ls+mod)%mod; } for(int i=p1;i<m;i++){ ls=b[b1][i]; b[b1][i]=(b[b1][i]+z)%mod; sum[b1]=(sum[b1]+b[b1][i]-ls+mod)%mod; } tagc[b1]=1;tagj[b1]=0; for(int i=b1+1;i<b2;i++) tagj[i]=(tagj[i]+z)%mod; for(int i=0;i<m;i++){ ls=b[b2][i]; b[b2][i]=(b[b2][i]*tagc[b2]+tagj[b2])%mod; sum[b2]=(sum[b2]+b[b2][i]-ls+mod)%mod; } for(int i=0;i<=p2;i++){ ls=b[b2][i]; b[b2][i]=(b[b2][i]+z)%mod; sum[b2]=(sum[b2]+b[b2][i]-ls+mod)%mod; } tagc[b2]=1;tagj[b2]=0; } } else{ x=read()-1;y=read()-1;ans=0; b1=x/m;b2=y/m; p1=x%m;p2=y%m; if(b1==b2){ for(int i=p1;i<=p2;i++){ ans=(ans+b[b1][i]*tagc[b1]%mod+tagj[b1])%mod; } } else{ for(int i=p1;i<m;i++){ ans=(ans+b[b1][i]*tagc[b1]+tagj[b1])%mod; } for(int i=b1+1;i<b2;i++){ ans=(ans+sum[i]*tagc[i]+tagj[i]*m)%mod; } for(int i=0;i<=p2;i++){ ans=(ans+b[b2][i]*tagc[b2]+tagj[b2])%mod; } } printf("%lld ",ans); } } return 0; }
//AC代码 //线段树：乘法标记优先级比加法高 #pra gma GCC optimize("O2") #include<cstdio> #define lc k<<1 #define rc k<<1|1 using namespace std; typedef long long ll; 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; } const int M=1e5+10,N=M<<2; struct node{ ll ans,fc,fj; }tr[N]; int n,m,mod,a[M]; void build(int k,int l,int r){ tr[k].fc=1;tr[k].fj=0; if(l==r){ tr[k].ans=a[l]%mod; return ; } int mid=l+r>>1; build(lc,l,mid); build(rc,mid+1,r); tr[k].ans=(tr[lc].ans+tr[rc].ans)%mod; } void pushdown(int k,int l,int r){ if((tr[k].fc==1&&tr[k].fj==0)||(l==r)) return ; int mid=l+r>>1; tr[lc].ans=(tr[lc].ans*tr[k].fc+(mid-l+1)*tr[k].fj)%mod; tr[rc].ans=(tr[rc].ans*tr[k].fc+(r-mid)*tr[k].fj)%mod; tr[lc].fc=tr[lc].fc*tr[k].fc%mod; tr[rc].fc=tr[rc].fc*tr[k].fc%mod; tr[lc].fj=(tr[k].fj+tr[lc].fj*tr[k].fc)%mod; tr[rc].fj=(tr[k].fj+tr[rc].fj*tr[k].fc)%mod; tr[k].fc=1;tr[k].fj=0; } void change_mul(int k,int l,int r,int x,int y,int v){ pushdown(k,l,r); if(l==x&&r==y){ tr[k].ans=tr[k].ans*v%mod; tr[k].fc=v%mod; return ; } int mid=l+r>>1; if(y<=mid) change_mul(lc,l,mid,x,y,v); else if(x>mid) change_mul(rc,mid+1,r,x,y,v); else change_mul(lc,l,mid,x,mid,v),change_mul(rc,mid+1,r,mid+1,y,v); tr[k].ans=(tr[lc].ans+tr[rc].ans)%mod; } void change_sum(int k,int l,int r,int x,int y,int v){ pushdown(k,l,r); if(l==x&&r==y){ tr[k].ans=(tr[k].ans+(r-l+1)*v)%mod; tr[k].fj=v%mod; return ; } int mid=l+r>>1; if(y<=mid) change_sum(lc,l,mid,x,y,v); else if(x>mid) change_sum(rc,mid+1,r,x,y,v); else change_sum(lc,l,mid,x,mid,v),change_sum(rc,mid+1,r,mid+1,y,v); tr[k].ans=(tr[lc].ans+tr[rc].ans)%mod; } int query_sum(int k,int l,int r,int x,int y){ pushdown(k,l,r); if(l==x&&r==y) return tr[k].ans%mod; int mid=l+r>>1; if(y<=mid) return query_sum(lc,l,mid,x,y); else if(x>mid) return query_sum(rc,mid+1,r,x,y); else return (query_sum(lc,l,mid,x,mid)+query_sum(rc,mid+1,r,mid+1,y))%mod; } int main(){ n=read();m=read();mod=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,1,n); for(int i=1,opt,x,y,z;i<=m;i++){ opt=read();x=read();y=read(); if(opt==1) z=read(),change_mul(1,1,n,x,y,z);else if(opt==2) z=read(),change_sum(1,1,n,x,y,z);else if(opt==3) printf("%d ",query_sum(1,1,n,x,y)); } return 0; }