摘要：
题意：有长为N的数列，不妨设为a1,a2,…思路：线段树,因为有可能存在，同时加和乘，所以lazy标记变为二维，一个记录乘，一个记录加因为乘是总和乘一个数，所以先乘再加，这里需要注意，因为原本的区间和可能是zhi+lazy，乘是总体，所以标记lazy也要乘ilvoidpushdown{if(lazy[x][1]!=0){intmid=(l+r)˃˃1;tree[x˂˂1]+=*lazy[x][0];tree[x˂˂1]%=mod;tree[x˂˂1|1]+=*lazy[x][0];tree[x˂˂1|1]%=mod;lazy[x˂˂1][0]+=lazy[x][0];lazy[x˂˂1][0]%=mod;lazy[x˂˂1|1][0]+=lazy[x][0];lazy[x˂˂1|1][0]%=mod;lazy[x][0]=0;}}这题也wa了好多遍，直到最后相通了，当加和乘同时存在的时候#includeusingnamespacestd;#definelllonglong#defineilinline#defineitregisterint#defineinf0x3f3f3f3f#definelowbit&(-x)#definemem(a,b)memset#definemodd998244353constintmaxn=2e5+10;intn,m,k;llp;lltree[maxn˂˂2],lazy[maxn˂˂2][2],a[maxn];ilvoidpushdown{if(lazy[x][1]!
题意：
有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：N<=1e5
(1)把数列中的一段数全部乘一个值;
(2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。
思路：
线段树,因为有可能存在，同时加和乘，所以lazy标记变为二维，一个记录乘，一个记录加
因为乘是总和乘一个数，所以先乘再加，这里需要注意，因为原本的区间和可能是zhi+lazy【加】，乘是总体，所以标记lazy【加】也要乘
il void pushdown(int x,ll mod,int l,intr){ if(lazy[x][1]!=1){ tree[x<<1]*=lazy[x][1];tree[x<<1]%=mod; tree[x<<1|1]*=lazy[x][1];tree[x<<1|1]%=mod; lazy[x<<1][1]*=lazy[x][1];lazy[x<<1][1]%=mod; lazy[x<<1|1][1]*=lazy[x][1];lazy[x<<1|1][1]%=mod; lazy[x<<1][0]*=lazy[x][1];lazy[x<<1][0]%=mod; lazy[x<<1|1][0]*=lazy[x][1];lazy[x<<1|1][0]%=mod; lazy[x][1]=1; } if(lazy[x][0]!=0){ int mid=(l+r)>>1; tree[x<<1]+=(mid-l+1)*lazy[x][0];tree[x<<1]%=mod; tree[x<<1|1]+=(r-mid)*lazy[x][0];tree[x<<1|1]%=mod; lazy[x<<1][0]+=lazy[x][0];lazy[x<<1][0]%=mod; lazy[x<<1|1][0]+=lazy[x][0];lazy[x<<1|1][0]%=mod; lazy[x][0]=0; } }
这题也wa了好多遍，直到最后相通了，当加和乘同时存在的时候
![P2023 [AHOI2009]维护序列 区间加乘模板第1张](https://img2018.cnblogs.com/common/1869627/202002/1869627-20200219191342673-2127339527.png)
#include<bits/stdc++.h> using namespacestd; #define ll long long #define il inline #define it register int #define inf 0x3f3f3f3f #define lowbit(x) (x)&(-x) #define mem(a,b) memset(a,b,sizeof(a)) #define modd 998244353 const int maxn=2e5+10; intn,m,k; ll p; ll tree[maxn<<2],lazy[maxn<<2][2],a[maxn]; il void pushdown(int x,ll mod,int l,intr){ if(lazy[x][1]!=1){ tree[x<<1]*=lazy[x][1];tree[x<<1]%=mod; tree[x<<1|1]*=lazy[x][1];tree[x<<1|1]%=mod; lazy[x<<1][1]*=lazy[x][1];lazy[x<<1][1]%=mod; lazy[x<<1|1][1]*=lazy[x][1];lazy[x<<1|1][1]%=mod; lazy[x<<1][0]*=lazy[x][1];lazy[x<<1][0]%=mod; lazy[x<<1|1][0]*=lazy[x][1];lazy[x<<1|1][0]%=mod; lazy[x][1]=1; } if(lazy[x][0]!=0){ int mid=(l+r)>>1; tree[x<<1]+=(mid-l+1)*lazy[x][0];tree[x<<1]%=mod; tree[x<<1|1]+=(r-mid)*lazy[x][0];tree[x<<1|1]%=mod; lazy[x<<1][0]+=lazy[x][0];lazy[x<<1][0]%=mod; lazy[x<<1|1][0]+=lazy[x][0];lazy[x<<1|1][0]%=mod; lazy[x][0]=0; } } il void pushup(intx,ll mod){ tree[x]=(tree[x<<1]+tree[x<<1|1])%mod; } void build(int x,int l,intr,ll mod){ lazy[x][1]=1;lazy[x][0]=0; if(l==r){ tree[x]=a[l];return; } int mid=(l+r)>>1; build(x<<1,l,mid,mod); build(x<<1|1,mid+1,r,mod); pushup(x,mod); } void updatej(int x,int l,int r,int l1,intr1,ll zhi,ll mod){ if(l1<=l && r<=r1){ pushdown(x,mod,l,r); lazy[x][0]=zhi;tree[x]+=(ll)(r-l+1)*zhi;tree[x]%=mod; return; } pushdown(x,mod,l,r); int mid=(l+r)>>1; if(l1<=mid){ updatej(x<<1,l,mid,l1,r1,zhi,mod); } if(r1>mid){ updatej(x<<1|1,mid+1,r,l1,r1,zhi,mod); } pushup(x,mod); } void updatec(int x,int l,int r,int l1,intr1,ll zhi,ll mod){ if(l1<=l && r<=r1){ pushdown(x,mod,l,r); lazy[x][1]=zhi;tree[x]*=zhi;tree[x]%=mod; return; } pushdown(x,mod,l,r); int mid=(l+r)>>1; if(l1<=mid){ updatec(x<<1,l,mid,l1,r1,zhi,mod); } if(r1>mid){ updatec(x<<1|1,mid+1,r,l1,r1,zhi,mod); } pushup(x,mod); } ll query(int x,int l,int r,int l1,intr1,ll mod){ if(l1<=l && r<=r1){ returntree[x]; } pushdown(x,mod,l,r); int mid=(l+r)>>1; ll sum=0; if(l1<=mid){ sum+=query(x<<1,l,mid,l1,r1,mod);sum%=mod; } if(r1>mid){ sum+=query(x<<1|1,mid+1,r,l1,r1,mod);sum%mod; } return sum%mod; } intmain(){ scanf("%d%lld",&n,&p); for(it i=1;i<=n;i++){ scanf("%lld",&a[i]);a[i]%=p; } build(1,1,n,p); scanf("%d",&m); while(m--){//cout<<tree[1]<<endl; intt,g; ll c; scanf("%d",&k); if(k==1){ scanf("%d%d%lld",&t,&g,&c); updatec(1,1,n,t,g,c%p,p); } else if(k==2){ scanf("%d%d%lld",&t,&g,&c); updatej(1,1,n,t,g,c%p,p); } else{ scanf("%d%d",&t,&g); printf("%lld ",query(1,1,n,t,g,p)); } } return 0; }