题意：
有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：N<=1e5
(1)把数列中的一段数全部乘一个值;
(2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。
思路：
线段树,因为有可能存在，同时加和乘，所以lazy标记变为二维，一个记录乘，一个记录加
因为乘是总和乘一个数，所以先乘再加，这里需要注意，因为原本的区间和可能是zhi+lazy【加】，乘是总体，所以标记lazy【加】也要乘
1 il void pushdown(int x,ll mod,int l,int r){ 2 if(lazy[x][1]!=1){ 3 tree[x<<1]*=lazy[x][1];tree[x<<1]%=mod; 4 tree[x<<1|1]*=lazy[x][1];tree[x<<1|1]%=mod; 5 lazy[x<<1][1]*=lazy[x][1];lazy[x<<1][1]%=mod; 6 lazy[x<<1|1][1]*=lazy[x][1];lazy[x<<1|1][1]%=mod; 7 lazy[x<<1][0]*=lazy[x][1];lazy[x<<1][0]%=mod; 8 lazy[x<<1|1][0]*=lazy[x][1];lazy[x<<1|1][0]%=mod; 9 lazy[x][1]=1; 10 } 11 if(lazy[x][0]!=0){ 12 int mid=(l+r)>>1; 13 tree[x<<1]+=(mid-l+1)*lazy[x][0];tree[x<<1]%=mod; 14 tree[x<<1|1]+=(r-mid)*lazy[x][0];tree[x<<1|1]%=mod; 15 lazy[x<<1][0]+=lazy[x][0];lazy[x<<1][0]%=mod; 16 lazy[x<<1|1][0]+=lazy[x][0];lazy[x<<1|1][0]%=mod; 17 lazy[x][0]=0; 18 } 19 }
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define il inline 5 #define it register int 6 #define inf 0x3f3f3f3f 7 #define lowbit(x) (x)&(-x) 8 #define mem(a,b) memset(a,b,sizeof(a)) 9 #define modd 998244353 10 const int maxn=2e5+10; 11 int n,m,k; 12 ll p; 13 ll tree[maxn<<2],lazy[maxn<<2][2],a[maxn]; 14 il void pushdown(int x,ll mod,int l,int r){ 15 if(lazy[x][1]!=1){ 16 tree[x<<1]*=lazy[x][1];tree[x<<1]%=mod; 17 tree[x<<1|1]*=lazy[x][1];tree[x<<1|1]%=mod; 18 lazy[x<<1][1]*=lazy[x][1];lazy[x<<1][1]%=mod; 19 lazy[x<<1|1][1]*=lazy[x][1];lazy[x<<1|1][1]%=mod; 20 lazy[x<<1][0]*=lazy[x][1];lazy[x<<1][0]%=mod; 21 lazy[x<<1|1][0]*=lazy[x][1];lazy[x<<1|1][0]%=mod; 22 lazy[x][1]=1; 23 } 24 if(lazy[x][0]!=0){ 25 int mid=(l+r)>>1; 26 tree[x<<1]+=(mid-l+1)*lazy[x][0];tree[x<<1]%=mod; 27 tree[x<<1|1]+=(r-mid)*lazy[x][0];tree[x<<1|1]%=mod; 28 lazy[x<<1][0]+=lazy[x][0];lazy[x<<1][0]%=mod; 29 lazy[x<<1|1][0]+=lazy[x][0];lazy[x<<1|1][0]%=mod; 30 lazy[x][0]=0; 31 } 32 } 33 il void pushup(int x,ll mod){ 34 tree[x]=(tree[x<<1]+tree[x<<1|1])%mod; 35 } 36 void build(int x,int l,int r,ll mod){ 37 lazy[x][1]=1;lazy[x][0]=0; 38 if(l==r){ 39 tree[x]=a[l];return; 40 } 41 int mid=(l+r)>>1; 42 build(x<<1,l,mid,mod); 43 build(x<<1|1,mid+1,r,mod); 44 pushup(x,mod); 45 } 46 void updatej(int x,int l,int r,int l1,int r1,ll zhi,ll mod){ 47 if(l1<=l && r<=r1){ 48 pushdown(x,mod,l,r); 49 lazy[x][0]=zhi;tree[x]+=(ll)(r-l+1)*zhi;tree[x]%=mod; 50 return; 51 } 52 pushdown(x,mod,l,r); 53 int mid=(l+r)>>1; 54 if(l1<=mid){ 55 updatej(x<<1,l,mid,l1,r1,zhi,mod); 56 } 57 if(r1>mid){ 58 updatej(x<<1|1,mid+1,r,l1,r1,zhi,mod); 59 } 60 pushup(x,mod); 61 } 62 void updatec(int x,int l,int r,int l1,int r1,ll zhi,ll mod){ 63 if(l1<=l && r<=r1){ 64 pushdown(x,mod,l,r); 65 lazy[x][1]=zhi;tree[x]*=zhi;tree[x]%=mod; 66 return; 67 } 68 pushdown(x,mod,l,r); 69 int mid=(l+r)>>1; 70 if(l1<=mid){ 71 updatec(x<<1,l,mid,l1,r1,zhi,mod); 72 } 73 if(r1>mid){ 74 updatec(x<<1|1,mid+1,r,l1,r1,zhi,mod); 75 } 76 pushup(x,mod); 77 } 78 ll query(int x,int l,int r,int l1,int r1,ll mod){ 79 if(l1<=l && r<=r1){ 80 return tree[x]; 81 } 82 pushdown(x,mod,l,r); 83 int mid=(l+r)>>1; 84 ll sum=0; 85 if(l1<=mid){ 86 sum+=query(x<<1,l,mid,l1,r1,mod);sum%=mod; 87 } 88 if(r1>mid){ 89 sum+=query(x<<1|1,mid+1,r,l1,r1,mod);sum%mod; 90 } 91 return sum%mod; 92 } 93 int main(){ 94 scanf("%d%lld",&n,&p); 95 for(it i=1;i<=n;i++){ 96 scanf("%lld",&a[i]);a[i]%=p; 97 } 98 build(1,1,n,p); 99 100 scanf("%d",&m); 101 while(m--){//cout<<tree[1]<<endl; 102 int t,g; 103 ll c; 104 scanf("%d",&k); 105 if(k==1){ 106 scanf("%d%d%lld",&t,&g,&c); 107 updatec(1,1,n,t,g,c%p,p); 108 } 109 else if(k==2){ 110 scanf("%d%d%lld",&t,&g,&c); 111 updatej(1,1,n,t,g,c%p,p); 112 } 113 else{ 114 scanf("%d%d",&t,&g); 115 printf("%lld\n",query(1,1,n,t,g,p)); 116 } 117 } 118 return 0; 119 }
这题也wa了好多遍，直到最后相通了，当加和乘同时存在的时候
原文：https://www.cnblogs.com/luoyugongxi/p/12332675.html
