首页 > 代码库 > 线段树模板合集(CodeVS1080 1081 1082 4597)Pascal代码
线段树模板合集(CodeVS1080 1081 1082 4597)Pascal代码
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.
线段树模板合集(CodeVS1080 1081 1082 4597)Pascal代码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。