博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
算法模板——线段树3(区间覆盖值+区间求和)
阅读量:5872 次
发布时间:2019-06-19

本文共 2541 字,大约阅读时间需要 8 分钟。

实现功能——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          begin10               if x
y then17 begin18 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 begin26 if l>r then exit(0);27 if (x=l) and (y=r) then28 begin29 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 begin41 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 begin48 if x=y then49 read(a[z])50 else51 begin52 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 begin59 readln(n,m);60 built(1,1,n);61 readln;62 for i:=1 to m do63 begin64 read(j);65 case j of66 1:begin67 readln(a1,a2,a3);68 op(1,1,n,a1,a2,a3);69 end;70 2:begin71 readln(a1,a2);72 writeln(cal(1,1,n,a1,a2));73 end;74 else halt;75 end;76 end;77 end.78

 

转载于:https://www.cnblogs.com/HansBug/p/4237715.html

你可能感兴趣的文章
Guice 练习 constructorbindings demo
查看>>
android aapt 用法 -- ApkReader
查看>>
[翻译]用 Puppet 搭建易管理的服务器基础架构(3)
查看>>
Android -- AudioPlayer
查看>>
Python大数据依赖包安装
查看>>
Android View.onMeasure方法的理解
查看>>
Node.js 爬虫初探
查看>>
ABP理论学习之仓储
查看>>
centos7下使用yum安装mysql
查看>>
How can I set ccshared=-fPIC while executing ./configure?
查看>>
2.移植uboot-添加2440单板,并实现NOR、NAND启动
查看>>
hadoop-2.6.5安装
查看>>
vmware虚拟机里的LINUX不能上网的原因一:虚拟网卡设置
查看>>
监控摄像机的区别和分类
查看>>
Java学习——对象和类
查看>>
ElasticSearch 组合过滤器
查看>>
HttpClient连接池的连接保持、超时和失效机制
查看>>
eigrp debug命令详解
查看>>
NFS配置文件
查看>>
J2ME程序员容易遇到的问题!不断更新中_2008.05.17
查看>>