题目描述
如题，已知一个数列，你需要进行下面两种操作：
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）
此题对我很有启迪作用，让我之前对线段树延迟标记的疑惑烟消云散，茅塞顿开。有一个很重要的地方：这个节点打上延迟标记的话这个节点是需要更新的
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <iostream> 9 #include "algorithm" 10 #define lson rt<<1,l,m 11 #define rson rt<<1|1,m+1,r 12 using namespace std; 13 typedef long long LL; 14 const int MAX=100005; 15 int n,m; 16 LL sum[MAX*6],la1[MAX*6],la2[MAX*6],mod; 17 void PushDown(int rt,int l,int r){ 18 if (l==r || (la2[rt]==0 && la1[rt]==1)) return; 19 int m=(l+r)>>1; 20 sum[rt<<1]=(sum[rt<<1]*la1[rt]+la2[rt]*(m-l+1))%mod; 21 sum[rt<<1|1]=(sum[rt<<1|1]*la1[rt]+la2[rt]*(r-m))%mod; 22 23 la2[rt<<1]=(la2[rt<<1]*la1[rt]+la2[rt])%mod; 24 la2[rt<<1|1]=(la2[rt<<1|1]*la1[rt]+la2[rt])%mod; 25 la2[rt]=0; 26 27 la1[rt<<1]=la1[rt<<1]*la1[rt]%mod;la1[rt<<1|1]=la1[rt<<1|1]*la1[rt]%mod; 28 la1[rt]=1; 29 } 30 void PushUp(int rt){ 31 sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod; 32 } 33 void build(int rt,int l,int r){ 34 la1[rt]=1;la2[rt]=0; 35 if (l==r){ 36 scanf("%lld",&sum[rt]); 37 return; 38 } 39 int m=(l+r)>>1; 40 build(lson); 41 build(rson); 42 PushUp(rt); 43 } 44 void Update1(int x,int y,int z,int rt,int l,int r){ 45 if (x<=l && r<=y){ 46 PushDown(rt,l,r); 47 la1[rt]=z; 48 sum[rt]=sum[rt]*(LL)z%mod; 49 return; 50 } 51 int m=(l+r)>>1; 52 PushDown(rt,l,r); 53 if (x<=m) Update1(x,y,z,lson); 54 if (y>m) Update1(x,y,z,rson); 55 PushUp(rt); 56 } 57 void Update2(int x,int y,int z,int rt,int l,int r){ 58 if (x<=l && r<=y){ 59 la2[rt]+=z; 60 sum[rt]=(sum[rt]+(LL)z*(r-l+1))%mod; 61 return; 62 } 63 int m=(l+r)>>1; 64 PushDown(rt,l,r); 65 if (x<=m) Update2(x,y,z,lson); 66 if (y>m) Update2(x,y,z,rson); 67 PushUp(rt); 68 } 69 LL search(int x,int y,int rt,int l,int r){ 70 if (x<=l && r<=y){ 71 return sum[rt]; 72 } 73 LL an=0; 74 int m=(l+r)>>1; 75 PushDown(rt,l,r); 76 if (x<=m) an=(an+search(x,y,lson))%mod; 77 if (y>m) an=(an+search(x,y,rson))%mod; 78 return an; 79 } 80 int main(){ 81 freopen ("treetwo.in","r",stdin); 82 freopen ("treetwo.out","w",stdout); 83 int i,j; 84 int x,y,z,w; 85 scanf("%d%d%d",&n,&m,&mod); 86 build(1,1,n); 87 for (i=1;i<=m;i++){ 88 scanf("%d",&w); 89 if (w==1){ 90 scanf("%d%d%d",&x,&y,&z); 91 Update1(x,y,z,1,1,n); 92 } 93 if (w==2){ 94 scanf("%d%d%d",&x,&y,&z); 95 Update2(x,y,z,1,1,n); 96 } 97 if (w==3){ 98 scanf("%d%d",&x,&y); 99 printf("%lld ",search(x,y,1,1,n)); 100 } 101 } 102 return 0; 103 }