专栏首页HansBug's Lab算法模板——线段树3(区间覆盖值+区间求和)

算法模板——线段树3(区间覆盖值+区间求和)

实现功能——1:区间覆盖值;2:区间求和

相比直接的区间加,这个要注重顺序,因为操作有顺序之分。所以这里面的tag应该有个pushup操作(本程序中的ext)

 1 var
 2    i,j,k,l,m,n,a1,a2,a3,a4:longint;
 3    a,b,d:array[0..100000] of longint;
 4 function max(x,y:longint):longint;inline;
 5          begin
 6               if x>y then max:=x else max:=y;
 7          end;
 8 function min(x,y:longint):longint;inline;
 9          begin
10               if x<y then min:=x else min:=y;
11          end;
12 procedure ext(z,x,y:longint);inline;
13           begin
14                if d[z]=0 then exit;
15                a[z]:=b[z]*(y-x+1);
16                if x<>y then
17                   begin
18                        b[z*2]:=b[z];d[z*2]:=1;
19                        b[z*2+1]:=b[z];d[z*2+1]:=1;
20                   end;
21                b[z]:=0;d[z]:=0;
22           end;
23 function op(z,x,y,l,r,p:longint):longint;inline;
24          var a3,a4:longint;
25          begin
26               if l>r then exit(0);
27               if (x=l) and (y=r) then
28                  begin
29                       if d[z]=1 then a[z]:=b[z]*(r-l+1);
30                       d[z]:=1;b[z]:=p;
31                       exit(p*(r-l+1)-a[z]);
32                  end;
33               ext(z,x,y);
34               a3:=op(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),p);
35               a4:=op(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,p);
36               a[z]:=a[z]+a3+a4;
37               exit(a3+a4);
38          end;
39 function cal(z,x,y,l,r:longint):longint;inline;
40          begin
41               if l>r then exit(0);
42               if d[z]=1 then exit(b[z]*(r-l+1));
43               if (x=l) and (y=r) then exit(a[z]);
44               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));
45          end;
46 procedure built(z,x,y:longint);inline;
47           begin
48                if x=y then
49                   read(a[z])
50                else
51                    begin
52                         built(z*2,x,(x+y) div 2);
53                         built(z*2+1,(x+y) div 2+1,y);
54                         a[z]:=a[z*2]+a[z*2+1];
55                    end;
56                b[z]:=0;d[z]:=0;
57           end;
58 begin
59      readln(n,m);
60      built(1,1,n);
61      readln;
62      for i:=1 to m do
63          begin
64               read(j);
65               case j of
66                    1:begin
67                           readln(a1,a2,a3);
68                           op(1,1,n,a1,a2,a3);
69                    end;
70                    2:begin
71                           readln(a1,a2);
72                           writeln(cal(1,1,n,a1,a2));
73                    end;
74                    else halt;
75               end;
76          end;
77 end.
78                   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2243: [SDOI2011]染色

    2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

    HansBug
  • 3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者

    3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者 Time Limit: 3 Sec  Memory Limit: 128...

    HansBug
  • 2929: [Poi1999]洞穴攀行

    2929: [Poi1999]洞穴攀行 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 80  Solved: ...

    HansBug
  • 1339 / 1163: [Baltic2008]Mafia

    1163: [Baltic2008]Mafia Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 96  Sol...

    HansBug
  • 3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者

    3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者 Time Limit: 3 Sec  Memory Limit: 128...

    HansBug
  • 1622: [Usaco2008 Open]Word Power 名字的能量

    1622: [Usaco2008 Open]Word Power 名字的能量 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

    HansBug
  • 3401: [Usaco2009 Mar]Look Up 仰望

    3401: [Usaco2009 Mar]Look Up 仰望 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: ...

    HansBug
  • 1934: [Shoi2007]Vote 善意的投票

    1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

    HansBug
  • 算法模板——线段树5(区间开根+区间求和)

    实现功能——1:区间开根;2:区间求和(此模板以BZOJ3038为例) 作为一个非常规的线段树操作,其tag也比较特殊呵呵哒 1 var 2 i,j,...

    HansBug
  • 2243: [SDOI2011]染色

    2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

    HansBug

扫码关注云+社区

领取腾讯云代金券