算法模板——线段树4（区间加+区间乘+区间覆盖值+区间求和）

浏览数：32 / 时间：2015年06月08日

实现功能——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 begin
102      readln(n,m);
103      built(1,1,n);
104      readln;
105      for i:=1 to m do
106          begin
107               read(j);
108               case j of
109                    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