首页 > 代码库 > 算法模板——线段树4（区间加+区间乘+区间覆盖值+区间求和）
算法模板——线段树4（区间加+区间乘+区间覆盖值+区间求和）
实现功能——1：区间加法 2：区间乘法 3：区间覆盖值 4：区间求和
这是个四种常见线段树功能的集合版哦。。。么么哒（其实只要协调好三种tag的关系并不算太难——前提是想明白了线段树的工作模式）
代码长度几经修改后也大为缩水
还有！！！——通过BZOJ1798反复的尝试，我的出来一个重要结论——尽量减少pushup操作的不必要使用次数，对于程序提速有明显的效果！！！
1 type vet=record 2 a0,a1:longint; 3 end; 4 var 5 i,j,k,l,m,n,a1,a2,a3:longint; 6 d1:vet; 7 a,b,d:array[0..100000] of longint; 8 c:array[0..100000] of vet; 9 function max(x,y:longint):longint;inline; 10 begin 11 if x>y then max:=x else max:=y; 12 end; 13 function min(x,y:longint):longint;inline; 14 begin 15 if x<y then min:=x else min:=y; 16 end; 17 function merge(d1,d2:vet):vet;inline; 18 var d3:vet; 19 begin 20 d3:=d1; 21 d3.a0:=d3.a0*d2.a0; 22 d3.a1:=d3.a1*d2.a0+d2.a1; 23 exit(d3); 24 end; 25 procedure ext(z,x,y:longint);inline; 26 begin 27 if d[z]=1 then 28 begin 29 a[z]:=b[z]*(y-x+1); 30 c[z].a0:=1;c[z].a1:=0; 31 if x<>y then 32 begin 33 b[z*2]:=b[z];d[z*2]:=1; 34 b[z*2+1]:=b[z];d[z*2+1]:=1; 35 end; 36 b[z]:=0;d[z]:=0; 37 end 38 else 39 begin 40 a[z]:=a[z]*c[z].a0+c[z].a1*(y-x+1); 41 if x<>y then 42 begin 43 if d[z*2]=1 then ext(z*2,x,(x+y) div 2); 44 if d[z*2+1]=1 then ext(z*2+1,(x+y) div 2+1,y); 45 c[z*2]:=merge(c[z*2],c[z]); 46 c[z*2+1]:=merge(c[z*2+1],c[z]); 47 end; 48 c[z].a0:=1;c[z].a1:=0; 49 end; 50 end; 51 procedure built(z,x,y:longint);inline; 52 begin 53 if x=y then 54 read(a[z]) 55 else 56 begin 57 built(z*2,x,(x+y) div 2); 58 built(z*2+1,(x+y) div 2+1,y); 59 a[z]:=a[z*2]+a[z*2+1]; 60 end; 61 b[z]:=0;d[z]:=0; 62 c[z].a0:=1;c[z].a1:=0; 63 end; 64 function op(z,x,y,l,r:longint;d1:vet):longint;inline; 65 var a2,a3:longint; 66 begin 67 if l>r then exit(0); 68 ext(z,x,y); 69 if (x=l) and (y=r) then 70 begin 71 c[z]:=d1; 72 exit((d1.a0-1)*a[z]+d1.a1*(r-l+1)); 73 end; 74 a2:=op(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),d1); 75 a3:=op(z*2+1,(x+y) div 2+1,y,max(l,(x+y) div 2+1),r,d1); 76 a[z]:=a[z]+a2+a3; 77 exit(a2+a3); 78 end; 79 function cover(z,x,y,l,r,p:longint):longint;inline; 80 var a2,a3:longint; 81 begin 82 if l>r then exit(0); 83 ext(z,x,y); 84 if (x=l) and (y=r) then 85 begin 86 d[z]:=1;b[z]:=p; 87 exit(p*(r-l+1)-a[z]); 88 end; 89 a2:=cover(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),p); 90 a3:=cover(z*2+1,(x+y) div 2+1,y,max(l,(x+y) div 2+1),r,p); 91 a[z]:=a[z]+a2+a3; 92 exit(a3+a2); 93 end; 94 function cal(z,x,y,l,r:longint):longint; 95 begin 96 if l>r then exit(0); 97 ext(z,x,y); 98 if (x=l)and (y=r) then exit(a[z]); 99 exit(cal(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2))+cal(z*2+1,(x+y) div 2+1,y,max(l,(x+y) div 2+1),r));100 end;101 begin102 readln(n,m);103 built(1,1,n);104 readln;105 for i:=1 to m do106 begin107 read(j);108 case j of109 1:begin //区间加110 readln(a1,a2,a3);111 d1.a0:=1;d1.a1:=a3;112 op(1,1,n,a1,a2,d1);113 end;114 2:begin //区间乘115 readln(a1,a2,a3);116 d1.a0:=a3;d1.a1:=0;117 op(1,1,n,a1,a2,d1);118 end;119 3:begin //区间覆盖值120 readln(a1,a2,a3);121 cover(1,1,n,a1,a2,a3);122 end;123 4:begin //区间求和124 readln(a1,a2);125 writeln(cal(1,1,n,a1,a2));126 end;127 else halt;128 end;129 end;130 end.131
算法模板——线段树4（区间加+区间乘+区间覆盖值+区间求和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。