线段树
打两个标记,一个记录乘法一个记录加法,根据乘法分配律可以得到:标记下传的时候要先传乘法的标记再传加法的标记,下传乘法的时候要同时将子节点的加法标记也乘对应的数。
然后总结一下我自己犯的错误
1.标记下传时 判断无标记之后直接不操作 而不是把标记加上去
2.线段树开始忘记build
3.开始的时候没有看到要取模
代码
#include <cstdio> #include <algorithm> using namespace std; const int N=300010,NUL=-657558; typedef long long LL; LL sum[N*4],plus[N*4],mul[N*4],a[N],L[N*4],R[N*4],mod,m,op,x1,y1,z1,n; void up(int x){sum[x]=(sum[x<<1]+sum[x<<1|1])%mod;} void down(int x){ if(mul[x]!=NUL) { (sum[x<<1]*=mul[x])%=mod; if(mul[x<<1]!=NUL) (mul[x<<1]*=mul[x])%=mod;else mul[x<<1]=mul[x]%mod; if(plus[x<<1]!=NUL) (plus[x<<1]*=mul[x])%=mod; (sum[x<<1|1]*=mul[x])%=mod; if(mul[x<<1|1]!=NUL) (mul[x<<1|1]*=mul[x])%=mod;else mul[x<<1|1]=mul[x]%mod; if(plus[x<<1|1]!=NUL) (plus[x<<1|1]*=mul[x])%=mod; } if(plus[x]!=NUL) { (sum[x<<1]+=plus[x]*(R[x<<1]-L[x<<1]+1)%mod)%=mod; if(plus[x<<1]!=NUL) (plus[x<<1]+=plus[x])%=mod;else plus[x<<1]=plus[x]%mod; (sum[x<<1|1]+=plus[x]*(R[x<<1|1]-L[x<<1|1]+1)%mod)%=mod; if(plus[x<<1|1]!=NUL) (plus[x<<1|1]+=plus[x])%=mod;else plus[x<<1|1]=plus[x]%mod; } mul[x]=plus[x]=NUL; } void build(int x,int l,int r){ plus[x]=mul[x]=NUL;L[x]=l;R[x]=r; if(l==r) {sum[x]=a[l]; return;} int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); up(x); } void change1(int x,int l,int r,int d){//plus int mid=(L[x]+R[x])>>1; if(l<=L[x] && R[x]<=r) { if(plus[x]!=NUL) (plus[x]+=d)%=mod;else plus[x]=d%mod; (sum[x]+=d*(R[x]-L[x]+1)%mod)%=mod; return; } down(x); if(mid<r) change1(x<<1|1,l,r,d); if(mid>=l) change1(x<<1,l,r,d); up(x); } void change2(int x,int l,int r,int d){//multiply int mid=(L[x]+R[x])>>1; if(l<=L[x] && R[x]<=r) { (sum[x]*=d%mod)%=mod; if(plus[x]!=NUL) (plus[x]*=d)%=mod; if(mul[x]!=NUL) (mul[x]*=d)%=mod; else mul[x]=d%mod; return; } down(x); if(mid<r) change2(x<<1|1,l,r,d); if(mid>=l) change2(x<<1,l,r,d); up(x); } LL ask(int x,int l,int r){ int mid=(L[x]+R[x])>>1; LL ret=0; if(l<=L[x] && R[x]<=r) return sum[x]; down(x); if(mid<r) (ret+=ask(x<<1|1,l,r))%=mod; if(mid>=l) (ret+=ask(x<<1,l,r))%=mod; return ret; } void print(){ for(int i=1;i<=n;i++) printf("%lld ",ask(1,i,i)); printf("\n"); } int main(){ //freopen("1798.in","r",stdin);freopen("1798.out","w",stdout); scanf("%lld%lld",&n,&mod); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,1,n); scanf("%lld",&m); for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&op,&x1,&y1); if(op==1) {scanf("%lld",&z1);change2(1,x1,y1,z1);} if(op==2) {scanf("%lld",&z1);change1(1,x1,y1,z1);} if(op==3) {printf("%lld\n",ask(1,x1,y1));} // print(); } return 0; }