题目大意：
有长为N的数列，有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。
思路：
用线段树来维护当前的值和要加以及乘的值，由于加与乘是有序的，所以要在做子树之前将标记下传（注意顺序），加和乘分开来、合起来处理都可以。
代码:（当初手抽将1打成l一直RE调了半天才发现）
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define MAX 400000 5 #define LL long long 6 using namespace std; 7 8 LL sum[MAX],mul[MAX],add[MAX],mod; 9 10 void up_date(int cur) 11 { 12 sum[cur]=(sum[cur<<1]+sum[cur<<1|1])%mod; 13 } 14 15 void creat(int L,int R,int x,int y,int cur) 16 { 17 mul[cur]=1; 18 add[cur]=0; 19 sum[cur]+=y; 20 if (L==R) return; 21 int mid=L+R>>1; 22 if (x>mid) creat(mid+1,R,x,y,cur<<1|1); 23 else creat(L,mid,x,y,cur<<1); 24 up_date(cur); 25 } 26 27 void push_down(int cur,int l,int r,int mid) 28 { 29 if (mul[cur]==1 && add[cur]==0) return; 30 mul[cur<<1]=mul[cur<<1]*mul[cur]%mod; 31 add[cur<<1]=(add[cur<<1]*mul[cur]%mod+add[cur])%mod; 32 sum[cur<<1]=(sum[cur<<1]*mul[cur]%mod+add[cur]*(LL)(mid-l+1)%mod)%mod; 33 mul[cur<<1|1]=mul[cur<<1|1]*mul[cur]%mod; 34 add[cur<<1|1]=(add[cur<<1|1]*mul[cur]%mod+add[cur])%mod; 35 sum[cur<<1|1]=(sum[cur<<1|1]*mul[cur]%mod+add[cur]*(LL)(r-mid)%mod)%mod; 36 mul[cur]=1; 37 add[cur]=0; 38 return; 39 } 40 41 void change_mul(int L,int R,int l,int r,int x,int cur) 42 { 43 if (L>=l && R<=r) 44 { 45 mul[cur]=mul[cur]*(LL)x%mod; 46 add[cur]=add[cur]*(LL)x%mod; 47 sum[cur]=sum[cur]*(LL)x%mod; 48 return; 49 } 50 int mid=L+R>>1; 51 push_down(cur,L,R,mid); 52 if (l<=mid) change_mul(L,mid,l,r,x,cur<<1); 53 if (r>mid) change_mul(mid+1,R,l,r,x,cur<<1|1); 54 up_date(cur); 55 } 56 57 void change_add(int L,int R,int l,int r,int x,int cur) 58 { 59 if (L>=l && R<=r) 60 { 61 add[cur]=(add[cur]+(LL)x)%mod; 62 sum[cur]=(sum[cur]+(LL)(R-L+1)*x%mod)%mod; 63 return; 64 } 65 int mid=L+R>>1; 66 push_down(cur,L,R,mid); 67 if (l<=mid) change_add(L,mid,l,r,x,cur<<1); 68 if (r>mid) change_add(mid+1,R,l,r,x,cur<<1|1); 69 up_date(cur); 70 } 71 72 LL ask(int L,int R,int l,int r,int cur) 73 { 74 if (L>=l && R<=r) return sum[cur]; 75 int mid=L+R>>1; 76 LL ans=0; 77 push_down(cur,L,R,mid); 78 if (l<=mid) ans=(ans+ask(L,mid,l,r,cur<<1))%mod; 79 if (r>mid) ans=(ans+ask(mid+1,R,l,r,cur<<1|1))%mod; 80 up_date(cur); 81 return ans; 82 } 83 84 int main() 85 { 86 int n,m,a,b,c,i,x; 87 scanf("%d%lld",&n,&mod); 88 for (i=1;i<=n;i++) scanf("%d",&a),creat(1,n,i,a%mod,1); 89 scanf("%d",&m); 90 for (i=1;i<=m;i++) 91 { 92 scanf("%d",&x); 93 if (x==1) scanf("%d%d%d",&a,&b,&c),change_mul(1,n,a,b,c%mod,1); 94 if (x==2) scanf("%d%d%d",&a,&b,&c),change_add(1,n,a,b,c%mod,1); 95 if (x==3) scanf("%d%d",&a,&b),printf("%lld\n",ask(1,n,a,b,1)); 96 } 97 return 0; 98 }
转载于:https://www.cnblogs.com/HHshy/p/5733943.html
相关资源：JAVA上百实例源码以及开源项目