线段树区间更新 lazy

1.

hdu1698

http://acm.hdu.edu.cn/showproblem.php?pid=1698

  1 /*
  2 x y k
  3 x~y的值变为k
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <time.h>
 10 #include <string>
 11 #include <set>
 12 #include <map>
 13 #include <list>
 14 #include <stack>
 15 #include <queue>
 16 #include <vector>
 17 #include <bitset>
 18 #include <ext/rope>
 19 #include <algorithm>
 20 #include <iostream>
 21 using namespace std;
 22 #define ll long long
 23 #define minv 1e-6
 24 #define inf 1e9
 25 #define pi 3.1415926536
 26 #define E  2.7182818284
 27 const ll mod=1e9+7;//998244353
 28 const int maxn=1e5+10;
 29 
 30 int tag[maxn<<2],sum[maxn<<2];
 31 
 32 void push_down(int index,int len)
 33 {
 34     tag[index<<1]=tag[index<<1|1]=tag[index];
 35     sum[index<<1]=((len+1)>>1)*tag[index];
 36     sum[index<<1|1]=(len>>1)*tag[index];
 37     tag[index]=0;
 38 }
 39 
 40 void build(int index,int l,int r)
 41 {
 42     tag[index]=0;
 43     if (l==r)
 44         sum[index]=1;
 45     else
 46     {
 47         int m=(l+r)>>1;
 48         build(index<<1,l,m);
 49         build(index<<1|1,m+1,r);
 50         sum[index]=sum[index<<1]+sum[index<<1|1];
 51     }
 52 }
 53 
 54 void update(int index,int l,int r,int x,int y,int k)
 55 {
 56     if (x<=l && r<=y)
 57     {
 58         tag[index]=k;
 59         sum[index]=(r-l+1)*k;
 60         return;
 61     }
 62     if (tag[index]!=0)
 63         push_down(index,r-l+1);
 64     int m=(l+r)>>1;
 65     if (x<=m)
 66         update(index<<1,l,m,x,y,k);
 67     if (m<y)
 68         update(index<<1|1,m+1,r,x,y,k);
 69     sum[index]=sum[index<<1]+sum[index<<1|1];
 70 }
 71 
 72 int query(int index,int l,int r,int s,int t)
 73 {
 74     if (s<=l && r<=t)
 75         return sum[index];
 76     if (r<s || l>t)
 77         return 0;
 78     if (tag[index]!=0)
 79         push_down(index,r-l+1);
 80     int m=(l+r)>>1;
 81     return query(index<<1,l,m,s,t)+query(index<<1|1,m+1,r,s,t);
 82 }
 83 
 84 int main()
 85 {
 86     int t,T,n,q,x,y,k;
 87     scanf("%d",&t);
 88     for (T=1;T<=t;T++)
 89     {
 90         scanf("%d",&n);
 91         build(1,1,n);
 92         scanf("%d",&q);
 93         while (q--)
 94         {
 95             scanf("%d%d%d",&x,&y,&k);
 96             update(1,1,n,x,y,k);
 97         }
 98         printf("Case %d: The total value of the hook is %d.
",T,query(1,1,n,1,n));
 99     }
100     return 0;
101 }

2.

https://www.luogu.org/problemnew/show/P3372

不用取余

  1 /*
  2 
  3 操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
  4 
  5 操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
  6 */
  7 #include <cstdio>
  8 #include <cstdlib>
  9 #include <cmath>
 10 #include <cstring>
 11 #include <time.h>
 12 #include <string>
 13 #include <set>
 14 #include <map>
 15 #include <list>
 16 #include <stack>
 17 #include <queue>
 18 #include <vector>
 19 #include <bitset>
 20 #include <ext/rope>
 21 #include <algorithm>
 22 #include <iostream>
 23 using namespace std;
 24 #define ll long long
 25 #define minv 1e-6
 26 #define inf 1e9
 27 #define pi 3.1415926536
 28 #define E  2.7182818284
 29 const ll mod=1e9+7;//998244353
 30 const int maxn=1e5+10;
 31 
 32 ll sum[maxn<<2],tag[maxn<<2];
 33 
 34 void build(int index,int l,int r)
 35 {
 36     tag[index]=0;
 37     if (l==r)
 38     {
 39         scanf("%lld",&sum[index]);
 40         sum[index]=sum[index];
 41     }
 42     else
 43     {
 44         int m=(l+r)>>1;
 45         build(index<<1,l,m);
 46         build(index<<1|1,m+1,r);
 47         sum[index]=sum[index<<1]+sum[index<<1|1];
 48     }
 49 }
 50 
 51 void pushdown(int index,ll len)
 52 {
 53     sum[index<<1]=tag[index]*((len+1)>>1) +sum[index<<1];
 54     sum[index<<1|1]=tag[index]*(len>>1) +sum[index<<1|1];
 55     tag[index<<1]=tag[index]+ tag[index<<1];
 56     tag[index<<1|1]=tag[index]+ tag[index<<1|1];
 57     tag[index]=0;
 58 }
 59 
 60 void update(int index,int l,int r,int x,int y,ll k)
 61 {
 62     if (x<=l && r<=y)
 63     {
 64         sum[index]=k*(r-l+1) +sum[index];
 65         tag[index]=k +tag[index];
 66         return;
 67     }
 68     int m=(l+r)>>1;
 69     if (tag[index]!=0)
 70         pushdown(index,r-l+1);
 71     if (x<=m)
 72         update(index<<1,l,m,x,y,k);
 73     if (m<y)
 74         update(index<<1|1,m+1,r,x,y,k);
 75     sum[index]=sum[index<<1]+sum[index<<1|1];
 76 }
 77 
 78 ll query(int index,int l,int r,int x,int y)
 79 {
 80     if (x<=l && r<=y)
 81         return sum[index];
 82     if (r<x || l>y)
 83         return 0;
 84     if (tag[index]!=0)
 85         pushdown(index,r-l+1);
 86     int m=(l+r)>>1;
 87     return query(index<<1,l,m,x,y)+query(index<<1|1,m+1,r,x,y);
 88 }
 89 
 90 int main()
 91 {
 92     int n,m,mode,x,y;
 93     ll k;
 94     scanf("%d%d",&n,&m);
 95     build(1,1,n);
 96     while (m--)
 97     {
 98         scanf("%d",&mode);
 99         if (mode==1)
100         {
101             scanf("%d%d%lld",&x,&y,&k);
102             update(1,1,n,x,y,k);
103         }
104         else
105         {
106             scanf("%d%d",&x,&y);
107             printf("%lld
",query(1,1,n,x,y));
108         }
109     }
110     return 0;
111 }
112 /*
113 10
114 463 793 740 374 330 772 681
115 5 8 39
116 5 8
117 3 6 3
118 5 8 90
119 1 5 21
120 3 8
121 3 8 17
122 4 7 52
123 2 6
124 2 7 41
125 5
126 2 3 4 5
127 1 3 -1
128 1 3 1
129 2 4
130 100
131 2 3 4 5 6 7 8 9 10
132 1 10
133 2 7 1
134 1 10
135 3 8
136 
137 */

3.

https://www.luogu.org/problemnew/show/P3373

  1 /*
  2 1.将某区间每一个数乘上x
  3 
  4 2.将某区间每一个数加上x
  5 
  6 3.求出某区间每一个数的和
  7 */
  8 #include <cstdio>
  9 #include <cstdlib>
 10 #include <cmath>
 11 #include <cstring>
 12 #include <time.h>
 13 #include <string>
 14 #include <set>
 15 #include <map>
 16 #include <list>
 17 #include <stack>
 18 #include <queue>
 19 #include <vector>
 20 #include <bitset>
 21 #include <ext/rope>
 22 #include <algorithm>
 23 #include <iostream>
 24 using namespace std;
 25 #define ll long long
 26 #define minv 1e-6
 27 #define inf 1e9
 28 #define pi 3.1415926536
 29 #define E  2.7182818284
 30 //const ll mod=1e9+7;//998244353
 31 const int maxn=1e5+10;
 32 
 33 ll mod;
 34 ll add[maxn<<2],mul[maxn<<2],sum[maxn<<2];
 35 int mode;
 36 
 37 void build(int index,int l,int r)
 38 {
 39     add[index]=0;
 40     mul[index]=1;
 41     if (l==r)
 42     {
 43         scanf("%lld",&sum[index]);
 44         sum[index]=sum[index]%mod;
 45     }
 46     else
 47     {
 48         int m=(l+r)>>1;
 49         build(index<<1,l,m);
 50         build(index<<1|1,m+1,r);
 51         sum[index]=(sum[index<<1]+sum[index<<1|1])%mod;
 52     }
 53 }
 54 
 55 void pushdown(int index,ll len)
 56 {
 57     //(x *y+z)*s+t = x*(ys) + z*s+t
 58     add[index<<1]=(add[index<<1]*mul[index]+add[index])%mod;
 59     mul[index<<1]=mul[index]*mul[index<<1]%mod;
 60     sum[index<<1]=(sum[index<<1]*mul[index]+add[index]*((len+1)>>1))%mod;
 61 
 62     add[index<<1|1]=(add[index<<1|1]*mul[index]+add[index])%mod;
 63     mul[index<<1|1]=mul[index]*mul[index<<1|1]%mod;
 64     sum[index<<1|1]=(sum[index<<1|1]*mul[index]+add[index]*(len>>1))%mod;
 65 
 66     add[index]=0;
 67     mul[index]=1;
 68 }
 69 
 70 void update(int index,int l,int r,int x,int y,ll k)
 71 {
 72     if (x<=l && r<=y)
 73     {
 74         if (mode==1)
 75         {
 76             //(x*y+z)*k
 77             sum[index]=sum[index]*k%mod;
 78             add[index]=add[index]*k%mod;
 79             mul[index]=mul[index]*k%mod;
 80         }
 81         else
 82         {
 83             //(x*y+z)+k
 84             sum[index]=(sum[index]+k*(r-l+1))%mod;
 85             add[index]=(add[index]+k)%mod;
 86         }
 87         return;
 88     }
 89     pushdown(index,r-l+1);
 90     int m=(l+r)>>1;
 91     if (x<=m)
 92         update(index<<1,l,m,x,y,k);
 93     if (m<y)
 94         update(index<<1|1,m+1,r,x,y,k);
 95     sum[index]=(sum[index<<1]+sum[index<<1|1])%mod;
 96 }
 97 
 98 ll query(int index,int l,int r,int x,int y)
 99 {
100     if (x<=l && r<=y)
101         return sum[index];
102     if (x>r || y<l)
103         return 0;
104     pushdown(index,r-l+1);
105     int m=(l+r)>>1;
106     return (query(index<<1,l,m,x,y)+query(index<<1|1,m+1,r,x,y))%mod;
107 }
108 
109 int main()
110 {
111     int n,q,x,y;
112     ll k;
113     scanf("%d%d%lld",&n,&q,&mod);
114     build(1,1,n);
115     while (q--)
116     {
117         scanf("%d%d%d",&mode,&x,&y);
118         if (mode!=3)
119         {
120             scanf("%lld",&k);
121             update(1,1,n,x,y,k%mod);
122         }
123         else
124             printf("%lld
",query(1,1,n,x,y));
125     }
126     return 0;
127 }
128 /*
129 5 100 1000000
130 1 2 3 4 5
131 1 1 5 2
132 2 1 5 3
133 3 1 3
134 
135 */
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cmyg/p/9567618.html