线段树初步

 

线段树模板1：https://www.luogu.org/problem/show?pid=3372

线段树模板2：https://www.luogu.org/problem/show?pid=3373

这些都比较基础，就是1或2个lazy标记的时候怎么处理？几乎不用考虑兼容性的问题。

现在这里有一道充分考验线段树lazy的兼容性问题的题目，涉及到4个lazy标记，怎么处理？

例子1：求线段树维护一个区间，支持如下操作：区间修改为同一个值（更改1），区间加一个数（更改2），区间和（运算1），区间最大值（运算2）：

解析：首先，不考虑lazy标记的兼容性是不行的，需要注意的是区间修改和区间和，区间最大值是不兼容的，所以在lazy时需要特判！！！

还有需要注意的点非常多，需要注意，

//本程序经过oycy0306测试正确性保障++
uses math;

const maxn=;

      inf=;

type rec=record

add,mk:longint;

end;

var  n,m,i,opx,opr,opl,ch,ans:longint;

     f,ff,a:array[..maxn]of longint;

     s:array[..maxn]of rec;

procedure build(x,l,r:longint);

var m:longint;

begin

 s[x].mk:=inf;

 s[x].add:=;

 if l=r then begin

  ff[x]:=a[l];

  f[x]:=a[l];

  exit;

 end;

 m:=(l+r)>>;

 build(*x,l,m);

 build(*x+,m+,r);

 f[x]:=f[*x]+f[*x+];

 ff[x]:=max(ff[*x],ff[*x+]);

end;

procedure down(x,l,r,m,lson,rson:longint);

begin

 if s[x].mk<>inf then begin  //**

  s[lson].mk:=s[x].mk;

  s[rson].mk:=s[x].mk;

  s[lson].add:=;

  s[rson].add:=;

  f[lson]:=opx*(m-l+);

  f[rson]:=opx*(r-m);

  ff[lson]:=opx;

  ff[rson]:=opx;

  s[x].mk:=inf;

  s[x].add:=;

  exit;

 end;

  s[lson].mk:=inf;

  s[rson].mk:=inf;

  s[lson].add:=s[lson].add+s[x].add;

  s[rson].add:=s[rson].add+s[x].add;

  f[lson]:=f[lson]+s[x].add*(m-l+);

  f[rson]:=f[rson]+s[x].add*(r-m);

  ff[lson]:=ff[lson]+s[x].add;

  ff[rson]:=ff[lson]+s[x].add;

  s[x].add:=;

  s[x].mk:=inf;             //**

end;

procedure calc(x,l,r:longint);

var m:longint;

begin

 if  (opl<=l)and(opr>=r) then begin

  case ch of

   :begin s[x].mk:=opx; s[x].add:=; f[x]:=opx*(r-l+); ff[x]:=opx; end;

   :begin s[x].add:=s[x].add+opx; f[x]:=f[x]+opx*(r-l+); ff[x]:=ff[x]+opx; end;

   :begin ans:=ans+f[x]; end;  //f:sum

   :begin ans:=max(ff[x],ans)end;  //ff:mk

  end;

  exit;

  end;

  m:=(l+r)>>;

  if (s[x].mk<>inf)or(s[x].add>)then down(x,l,r,m,*x,*x+);

  if opl<=m then calc(*x,l,m);

  if opr>m then calc(*x+,m+,r);

  if (ch=)or(ch=) then begin

   f[x]:=f[*x]+f[*x+];

   ff[x]:=max(ff[*x],ff[*x+])

  end;

end;

begin

 writeln('input nodenum n=??'); readln(n);

 writeln('input a num(n) sequence called a[]==??');

 for i:= to n do read(a[i]);

 write('the strat sequence a[]==');

 for i:= to n do write(a[i],' ');writeln;

 writeln('---------------------------');

 writeln('start to build XD tree.');

 writeln('---------------------------');

 build(,,n);

 writeln('---------------------------');

 writeln('XD tree is already built.');

 writeln('---------------------------');

 writeln('input your instructions number!'); //build ok!

 readln(m); writeln('OK.');

 writeln('---------------------------');

 writeln('1=modify');

 writeln('2=ADD');

 writeln('3=question sum');

 writeln('4=max in the a[]');

 writeln('a line a word.');

 writeln('instruction+ +minl+ +maxr+ (+valuable)');

 writeln('---------------------------');

 for i:= to m do begin

  writeln('instruction input ',i,' :');

  read(ch,opl,opr);

  if (ch=)or(ch=) then readln else readln(opx);

  case ch of

   ,:begin writeln('instruction output ',i,':'); writeln('Nothing except the instruction is running over.');calc(,,n); end;

   ,:begin ans:=; calc(,,n); writeln('instruction output ',i,' :'); writeln(ans); end;

  end;

 end;

end.

 例子2：求线段树维护一个区间，支持如下操作：区间修改为同一个值（更改1），区间加一个数（更改2），区间乘一个数（更该3），区间和（运算1），区间最大值（运算2）：、

对于例子一又多了一个区间乘法，所以就有5个lazy标记了...

所以这个down函数比较的长； 具体不解释了，就是在例子1上增加，看代码：

uses math;

const maxn=;

      inf=;

type rec=record

add,mk,mp:longint;

end;

var  n,m,i,opx,opr,opl,ch,ans:longint;

     f,ff,a:array[..maxn]of longint;

     s:array[..maxn]of rec;

procedure build(x,l,r:longint);

var m:longint;

begin

 s[x].mk:=inf;

 s[x].add:=;

 s[x].mp:=;

 if l=r then begin

  ff[x]:=a[l];

  f[x]:=a[l];

//  s[x].mx:=a[l];

  exit;

 end;

 m:=(l+r)>>;

 build(*x,l,m);

 build(*x+,m+,r);

 f[x]:=f[*x]+f[*x+];

 ff[x]:=max(ff[*x],ff[*x+]);

end;

procedure down(x,l,r,m,lson,rson:longint);

begin

 if s[x].mk<>inf then begin  //**

  s[lson].mk:=s[x].mk;

  s[rson].mk:=s[x].mk;

  s[lson].add:=;

  s[rson].add:=;

  s[lson].mp:=;

  s[rson].mp:=;

  f[lson]:=opx*(m-l+);

  f[rson]:=opx*(r-m);

  ff[lson]:=opx;

  ff[rson]:=opx;

  s[x].mk:=inf;

  s[x].add:=;

  s[x].mp:=;

  exit;

 end;

  s[lson].mp:=s[lson].mp*s[x].mp;

  s[rson].mp:=s[rson].mp*s[x].mp;

  s[lson].add:=s[lson].add*s[x].mp;

  s[rson].add:=s[rson].add*s[x].mp;

  f[lson]:=f[lson]*s[x].mp;

  f[rson]:=f[rson]*s[x].mp;

  ff[lson]:=ff[lson]*s[x].mp;

  ff[rson]:=ff[lson]*s[x].mp;

  s[x].mp:=;

  s[lson].mk:=inf;

  s[rson].mk:=inf;

  s[lson].add:=s[lson].add+s[x].add;

  s[rson].add:=s[rson].add+s[x].add;

  f[lson]:=f[lson]+s[x].add*(m-l+);

  f[rson]:=f[rson]+s[x].add*(r-m);

  ff[lson]:=ff[lson]+s[x].add;

  ff[rson]:=ff[lson]+s[x].add;

  s[x].add:=;

  s[x].mk:=inf;             //**

end;

procedure calc(x,l,r:longint);

var m:longint;

begin

 if  (opl<=l)and(opr>=r) then begin

  case ch of

   :begin s[x].mk:=opx; s[x].add:=; f[x]:=opx*(r-l+); ff[x]:=opx; end;

   :begin s[x].add:=s[x].add+opx; f[x]:=f[x]+opx*(r-l+); ff[x]:=ff[x]+opx; end;

   :begin ans:=ans+f[x]; end;  //f:sum

   :begin ans:=max(ff[x],ans)end;  //ff:mk

   :begin s[x].mp:=s[x].mp*opx; s[x].add:=s[x].add*opx; f[x]:=f[x]*opx; ff[x]:=ff[x]*opx; end;

  end;

  exit;

  end;

  m:=(l+r)>>;

  if (s[x].mk<>inf)or(s[x].add>)or(s[x].mp<>)then down(x,l,r,m,*x,*x+);

  if opl<=m then calc(*x,l,m);

  if opr>m then calc(*x+,m+,r);

  if (ch=)or(ch=) then begin

   f[x]:=f[*x]+f[*x+];

   ff[x]:=max(ff[*x],ff[*x+])

  end;

end;

begin

 writeln('input nodenum n=??'); readln(n);

 writeln('input a num(n) sequence called a[]==??');

 for i:= to n do read(a[i]);

 write('the strat sequence a[]==');

 for i:= to n do write(a[i],' ');writeln;

 writeln('---------------------------');

 writeln('start to build XD tree.');

 writeln('---------------------------');

 build(,,n);

 writeln('---------------------------');

 writeln('XD tree is already built.');

 writeln('---------------------------');

 writeln('input your instructions number!'); //build ok!

 readln(m); writeln('OK.');

 writeln('---------------------------');

 writeln('1=modify');

 writeln('2=ADD');

 writeln('3=question sum');

 writeln('4=max in the a[]');

 writeln('5=multiplication');

 writeln('a line a word.');

 writeln('instruction+ +minl+ +maxr+ (+valuable)');

 writeln('---------------------------');

 for i:= to m do begin

  writeln('instruction input ',i,' :');

  read(ch,opl,opr);

  if (ch=)or(ch=) then readln else readln(opx);

  case ch of

   ,,:begin calc(,,n); writeln('instruction output ',i,':'); writeln('Nothing except the instruction is running over.'); end;

   ,:begin ans:=; calc(,,n); writeln('instruction output ',i,' :'); writeln(ans); end;

  end;

 end;

end.
 
 

最新文章

  1. c++ 指针常量，常量指针
  2. ZFIR054-现金流量表
  3. ccc2016
  4. mysql导出导入某张表
  5. marvell笔试题(嵌入式软件)
  6. python 整型--《Python 3程序开发指南》笔记
  7. 人工神经网络简介和单层网络实现AND运算--AForge.NET框架的使用（五）
  8. 原生sql语句执行
  9. springmvc的ModelAndView的简单使用
  10. Mysql实战面试题
  11. ELK + Filebeat 日志分析系统
  12. Git常用命令（一）
  13. Django最简单的从请求过程
  14. Error resolving template [xxx], template might not exist or might not be exist
  15. struct sock注释
  16. swift 学习- 19 -- 可选链式调用
  17. 网络通信协议五之IP协议详解
  18. 3.Appnium的安装
  19. 学习JS的心路历程-参数的传递（下）
  20. 关于python-生成HTMLTestRunner测试报告

热门文章

  1. MYSQL---触发器简单了解
  2. spring-cloud 学习一 介绍
  3. 简单了解soap协议
  4. python之uWSGI和WSGI
  5. httpclient 多附件上传
  6. Sublime Text 3：自定义语法高亮
  7. webconfig中的&amp;符号问题解决
  8. mint-ui下拉加载min和上拉刷新（demo实例）
  9. Delphi 图形图像对象组件
  10. Tensorflow模型代码调试问题