首页 > 代码库 > [模板]洛谷T3373 线段树 模板2
[模板]洛谷T3373 线段树 模板2
此题相对于模板一，加了个区间乘，于是在模板一的基础上需要多开个数组（记录乘法懒标记）、多写个函数（区间乘），还有要把懒标记下放函数做些修改。
变量定义：
sum[]：线段树节点对应区间的元素总和；
addv[]：线段树节点对应区间的所有元素待加的值（懒标记），初值全部设为0；
mulv[]：线段树节点对应区间的所有元素待乘的值（懒标记），初值全部设为1。
过程说明：
建树（Build）：
同模板一。。。
懒标记下放（Push_down）：
原理解释：
1.当对某区间执行加法操作时，由于加法优先级低，不会对乘法操作产生影响，故直接相加即可；
2.当对某区间执行乘法操作时，由于乘法优先级高，会对之前的加法操作产生影响，故需要在相乘时不仅对sum和mulv相乘，也需要对addv相乘；
3.由于上述原因，故需要先算乘法再算加法。
细节实现：
1.子树的sum、mulv、addv值分别乘上当前节点的mulv值；
2.当前节点的mulv值还原，即置为1；
3.子树的addv值加上当前节点的addv值；
4.子树的sum值加上（子树包含元素数量*当前节点的addv值）；
5.当前节点的addv值还原，即置为0。
特别说明：
1.使用前判断，若当前节点的懒标记为空则不需执行此下放函数。虽然执行了也不会有影响，但浪费时间；
2.为尽量节省时间，要将判断放在此函数外而不是函数内。
区间加（Addall）：
同模板一。。。
区间乘（Mulall）：
若当前节点完全包含在待更新区间内，则直接修改当前节点的mulv、addv、sum值即可（参考下放函数说明）；
否则执行与区间加类似的操作即可。
区间查询（Query）：
同模板一。。。
提示：不要忘记取模。。。
代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<ctime> 5 #include<cstdlib> 6 #include<cmath> 7 #include<algorithm> 8 #include<string> 9 #include<stack> 10 #include<queue> 11 #include<vector> 12 #include<map> 13 using namespace std; 14 long long c[500010]; 15 long long p; 16 struct sgt{ 17 long long sum[2000010]; 18 long long addv[2000010]; 19 long long mulv[2000010]; 20 void build(int o,int l,int r){ 21 addv[o]=0; 22 mulv[o]=1; 23 if(l==r)sum[o]=c[l]; 24 else{ 25 int mid=(l+r)>>1; 26 int lson=o<<1; 27 int rson=lson|1; 28 build(lson,l,mid); 29 build(rson,mid+1,r); 30 sum[o]=(sum[lson]+sum[rson])%p; 31 } 32 } 33 void push_down(int o,int l,int r,int mid,int lson,int rson){ 34 mulv[lson]=(mulv[lson]*mulv[o])%p; 35 mulv[rson]=(mulv[rson]*mulv[o])%p; 36 addv[lson]=(addv[lson]*mulv[o])%p; 37 addv[rson]=(addv[rson]*mulv[o])%p; 38 sum[lson]=(sum[lson]*mulv[o])%p; 39 sum[rson]=(sum[rson]*mulv[o])%p; 40 mulv[o]=1; 41 addv[lson]=(addv[lson]+addv[o])%p; 42 addv[rson]=(addv[rson]+addv[o])%p; 43 sum[lson]=(sum[lson]+(mid-l+1)*addv[o])%p; 44 sum[rson]=(sum[rson]+(r-mid)*addv[o])%p; 45 addv[o]=0; 46 } 47 void addall(int o,int l,int r,int a,int b,int x){ 48 if(l>=a && r<=b){ 49 addv[o]=(addv[o]+x)%p; 50 sum[o]=(sum[o]+(r-l+1)*x)%p; 51 return; 52 } 53 else{ 54 int mid=(l+r)>>1; 55 int lson=o<<1; 56 int rson=lson|1; 57 if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson); 58 if(a<=mid)addall(lson,l,mid,a,b,x); 59 if(b>mid)addall(rson,mid+1,r,a,b,x); 60 sum[o]=(sum[lson]+sum[rson])%p; 61 } 62 } 63 void mulall(int o,int l,int r,int a,int b,int x){ 64 if(l>=a && r<=b){ 65 mulv[o]=(mulv[o]*x)%p; 66 addv[o]=(addv[o]*x)%p; 67 sum[o]=(sum[o]*x)%p; 68 return; 69 } 70 else{ 71 int mid=(l+r)>>1; 72 int lson=o<<1; 73 int rson=lson|1; 74 if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson); 75 if(a<=mid)mulall(lson,l,mid,a,b,x); 76 if(b>mid)mulall(rson,mid+1,r,a,b,x); 77 sum[o]=(sum[lson]+sum[rson])%p; 78 } 79 } 80 long long query(int o,int l,int r,int a,int b){ 81 if(l>=a && r<=b)return sum[o]%p; 82 else{ 83 int mid=(l+r)>>1; 84 int lson=o<<1; 85 int rson=lson|1; 86 long long ans=0; 87 if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson); 88 if(a<=mid)ans+=query(lson,l,mid,a,b); 89 if(b>mid)ans+=query(rson,mid+1,r,a,b); 90 return ans%p; 91 } 92 } 93 }; 94 sgt tree; 95 int n,m,i,f; 96 int x,y; 97 long long k; 98 int main(){ 99 scanf("%d%d%d",&n,&m,&p); 100 for(i=1;i<=n;i++)scanf("%d",&c[i]); 101 tree.build(1,1,n); 102 for(i=1;i<=m;i++){ 103 scanf("%d",&f); 104 switch(f){ 105 case 1:{ 106 scanf("%d%d%d",&x,&y,&k); 107 tree.mulall(1,1,n,x,y,k); 108 break; 109 } 110 case 2:{ 111 scanf("%d%d%d",&x,&y,&k); 112 tree.addall(1,1,n,x,y,k); 113 break; 114 } 115 case 3:{ 116 scanf("%d%d",&x,&y); 117 printf("%lld\n",tree.query(1,1,n,x,y)); 118 break; 119 } 120 } 121 } 122 return 0; 123 }
[模板]洛谷T3373 线段树 模板2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。