线段树模板合集(CodeVS1080 1081 1082 4597 1299)Pascal代码

在此之前,首先感谢CXK、ZN、HQY大神给予的代码支持!

var sum,flag,a,mn:array[0..800000] of int64;
var n,m,x,y,z,c:int64;
var i:longint;
function max(a,b:int64):int64;
begin
  if a>b then exit(a);exit(b);
end;
function min(a,b:int64):int64;
begin
  if a<b then exit(a);exit(b);
end;
procedure change(h:int64);
begin
  sum[h]:=sum[h<<1]+sum[h<<1+1];
  mn[h]:=min(mn[h<<1],mn[h<<1+1]);{max}
end;
procedure build(l,r,h:int64);//建树
var m:int64;
begin
  if l=r then begin sum[h]:=a[l];mn[h]:=a[l];exit;end;
  m:=(l+r)>>1;build(l,m,h<<1);build(m+1,r,(h<<1) or 1);
  change(h);
end;
procedure add(x,c,l,r,h:int64);//单点修改(加法运算){括号内为减法运算}
var m:int64;
begin
  if l=r then begin inc(sum[h],c);{dec}inc(mn[h],c);{dec}exit;end;
  m:=(l+r)>>1;if x<=m then add(x,c,l,m,h<<1) else add(x,c,m+1,r,(h<<1) or 1);
  change(h);
end;
procedure pushdown(h,l,r:int64);//下推(加法运算){括号内为减法运算}
begin
  if flag[h]<>0 then
  begin
    inc(flag[h<<1],flag[h]);
    inc(flag[(h<<1) or 1],flag[h]);
    inc(sum[h<<1],flag[h]*l);{dec}
    inc(sum[(h<<1) or 1],flag[h]*r);{dec}
    inc(mn[h<<1],flag[h]);{dec}
    inc(mn[(h<<1) or 1],flag[h]);{dec}
    flag[h]:=0;
  end;
end;
procedure range_add(x,y,c,l,r,h:int64);//区间相加{括号内为相减}
var m:int64;
begin
  if (x<=l) and (r<=y) then
  begin
    inc(sum[h],c*(r-l+1));{dec}
    inc(mn[h],c); {dec}
    inc(flag[h],c);
    exit;
  end;
  m:=(l+r)>>1;pushdown(h,m-l+1,r-m);
  if x<=m then range_add(x,y,c,l,m,h<<1);
  if y>m then range_add(x,y,c,m+1,r,(h<<1) or 1);
  change(h);
end;
function worksum(x,y,l,r,h:int64):int64;//区间求和
var m,ans:int64;
begin
  if (x<=l) and (r<=y) then exit(sum[h]);
  m:=(l+r)>>1;pushdown(h,m-l+1,r-m);ans:=0;
  if x<=m then inc(ans,worksum(x,y,l,m,h<<1));
  if y>m then inc(ans,worksum(x,y,m+1,r,(h<<1) or 1));
  exit(ans);
end;
function workmin(x,y,l,r,h:int64):int64;{max}//区间求最小值{括号内为最大值}
var m,ans:int64;
begin
  if (x<=l) and (r<=y) then exit(mn[h]);
  m:=(l+r)>>1;pushdown(h,m-l+1,r-m);
  ans:=maxlongint;{-maxlongint}
  if x<=m then ans:=min(ans,workmin(x,y,l,m,h<<1));{max}
  if y>m then ans:=min(ans,workmin(x,y,m+1,r,(h<<1) or 1));{max}
  exit(ans);
end;
procedure input;
begin
  read(n);for i:=1 to n do read(a[i]);build(1,n,1);
end;
procedure p1080;
begin
  input;read(m);
  for i:=1 to m do
  begin
    read(x,y,z);
    if x=1 then add(y,z,1,n,1);
    if x=2 then writeln(worksum(y,z,1,n,1));
  end;
end;
procedure p1081;
begin
  input;read(m);
  for i:=1 to m do
  begin
    read(x);
    if x=1 then begin read(y,z,c);range_add(y,z,c,1,n,1);end;
    if x=2 then begin read(y);writeln(worksum(y,y,1,n,1));end;
  end;
end;
procedure p1082;
begin
  input;read(m);
  for i:=1 to m do
  begin
    read(x);
    if x=1 then begin read(y,z,c);range_add(y,z,c,1,n,1);end;
    if x=2 then begin read(y,z);writeln(worksum(y,z,1,n,1));end;
  end;
end; 
procedure p4597;
var n,q,l,r,p:int64;
var i:longint;
var c:char;
begin
  readln(n,q);
  for i:=1 to n do read(a[i]); readln;
  build(1,n,1);
  for i:=1 to q do
   begin
    read(c);
    if c='M' then begin readln(l,r);;writeln(workmin(l,r,1,n,1));end;
    if c='S' then begin readln(l,r);writeln(worksum(l,r,1,n,1));end;
    if c='P' then begin readln(l,r,p);range_add(l,r,p,1,n,1);end;
   end;
end;
begin
  //主程序
end.

最后还有CodeVS1299切水果

var sum,flag:array[0..2000000] of longint;
var r1:array[0..2000000] of boolean;
var n,m,x,y:int64;
var i:longint;
procedure set1(h,l,r,x,y,num:longint);
var m,p:longint;
begin
  p:=0;
  if (l>=x) and (r<=y) then begin flag[h]:=num;r1[h]:=true;exit;end;
  m:=(l+r)>>1;
  if (x<=m) and (not r1[h<<1]) then set1(h<<1,l,m,x,y,num);
  if (y>m) and (not r1[h<<1+1]) then set1(h<<1+1,m+1,r,x,y,num);
  if r1[h<<1] then p:=(m-l+1)*flag[h<<1] else p:=sum[h<<1];
  if r1[h<<1+1] then inc(p,(r-m)*flag[h<<1+1]) else inc(p,sum[h<<1+1]);
  sum[h]:=p;
end;
begin
  read(n,m);
  for i:=1 to m do
  begin
    read(x,y);
    set1(1,1,n,x,y,1);
    writeln(n-sum[1]);
  end;
end.
  

  

原文地址:https://www.cnblogs.com/ligen1353055672/p/6293986.html