线段树模板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=1000; inf=233333333; type rec=record add,mk:longint; end; var n,m,i,opx,opr,opl,ch,ans:longint; f,ff,a:array[1..maxn]of longint; s:array[1..maxn]of rec; procedure build(x,l,r:longint); var m:longint; begin s[x].mk:=inf; s[x].add:=0; if l=r then begin ff[x]:=a[l]; f[x]:=a[l]; exit; end; m:=(l+r)>>1; build(2*x,l,m); build(2*x+1,m+1,r); f[x]:=f[2*x]+f[2*x+1]; ff[x]:=max(ff[2*x],ff[2*x+1]); 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:=0; s[rson].add:=0; f[lson]:=opx*(m-l+1); f[rson]:=opx*(r-m); ff[lson]:=opx; ff[rson]:=opx; s[x].mk:=inf; s[x].add:=0; 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+1); 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:=0; 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 1:begin s[x].mk:=opx; s[x].add:=0; f[x]:=opx*(r-l+1); ff[x]:=opx; end; 2:begin s[x].add:=s[x].add+opx; f[x]:=f[x]+opx*(r-l+1); ff[x]:=ff[x]+opx; end; 3:begin ans:=ans+f[x]; end; //f:sum 4:begin ans:=max(ff[x],ans)end; //ff:mk end; exit; end; m:=(l+r)>>1; if (s[x].mk<>inf)or(s[x].add>0)then down(x,l,r,m,2*x,2*x+1); if opl<=m then calc(2*x,l,m); if opr>m then calc(2*x+1,m+1,r); if (ch=1)or(ch=2) then begin f[x]:=f[2*x]+f[2*x+1]; ff[x]:=max(ff[2*x],ff[2*x+1]) end; end; begin writeln('input nodenum n=??'); readln(n); writeln('input a num(n) sequence called a[]==??'); for i:=1 to n do read(a[i]); write('the strat sequence a[]=='); for i:=1 to n do write(a[i],' ');writeln; writeln('---------------------------'); writeln('start to build XD tree.'); writeln('---------------------------'); build(1,1,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:=1 to m do begin writeln('instruction input ',i,' :'); read(ch,opl,opr); if (ch=3)or(ch=4) then readln else readln(opx); case ch of 1,2:begin writeln('instruction output ',i,':'); writeln('Nothing except the instruction is running over.');calc(1,1,n); end; 3,4:begin ans:=0; calc(1,1,n); writeln('instruction output ',i,' :'); writeln(ans); end; end; end; end.
例子2：求线段树维护一个区间，支持如下操作：区间修改为同一个值（更改1），区间加一个数（更改2），区间乘一个数（更该3），区间和（运算1），区间最大值（运算2）：、
对于例子1又多了一个区间乘法，所以就有5个lazy标记了...
所以这个down函数比较的长； 具体不解释了，就是在例子1上增加，看代码：
uses math; const maxn=1000; inf=233333333; type rec=record add,mk,mp:longint; end; var n,m,i,opx,opr,opl,ch,ans:longint; f,ff,a:array[1..maxn]of longint; s:array[1..maxn]of rec; procedure build(x,l,r:longint); var m:longint; begin s[x].mk:=inf; s[x].add:=0; s[x].mp:=1; if l=r then begin ff[x]:=a[l]; f[x]:=a[l]; // s[x].mx:=a[l]; exit; end; m:=(l+r)>>1; build(2*x,l,m); build(2*x+1,m+1,r); f[x]:=f[2*x]+f[2*x+1]; ff[x]:=max(ff[2*x],ff[2*x+1]); 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:=0; s[rson].add:=0; s[lson].mp:=1; s[rson].mp:=1; f[lson]:=opx*(m-l+1); f[rson]:=opx*(r-m); ff[lson]:=opx; ff[rson]:=opx; s[x].mk:=inf; s[x].add:=0; s[x].mp:=1; 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:=1; 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+1); 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:=0; 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 1:begin s[x].mk:=opx; s[x].add:=0; f[x]:=opx*(r-l+1); ff[x]:=opx; end; 2:begin s[x].add:=s[x].add+opx; f[x]:=f[x]+opx*(r-l+1); ff[x]:=ff[x]+opx; end; 3:begin ans:=ans+f[x]; end; //f:sum 4:begin ans:=max(ff[x],ans)end; //ff:mk 5: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)>>1; if (s[x].mk<>inf)or(s[x].add>0)or(s[x].mp<>1)then down(x,l,r,m,2*x,2*x+1); if opl<=m then calc(2*x,l,m); if opr>m then calc(2*x+1,m+1,r); if (ch=1)or(ch=2) then begin f[x]:=f[2*x]+f[2*x+1]; ff[x]:=max(ff[2*x],ff[2*x+1]) end; end; begin writeln('input nodenum n=??'); readln(n); writeln('input a num(n) sequence called a[]==??'); for i:=1 to n do read(a[i]); write('the strat sequence a[]=='); for i:=1 to n do write(a[i],' ');writeln; writeln('---------------------------'); writeln('start to build XD tree.'); writeln('---------------------------'); build(1,1,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:=1 to m do begin writeln('instruction input ',i,' :'); read(ch,opl,opr); if (ch=3)or(ch=4) then readln else readln(opx); case ch of 1,2,5:begin calc(1,1,n); writeln('instruction output ',i,':'); writeln('Nothing except the instruction is running over.'); end; 3,4:begin ans:=0; calc(1,1,n); writeln('instruction output ',i,' :'); writeln(ans); end; end; end; end.
例子3：区间加等比数列，区间和
我们用4个参数来描述加上的一个等比数列：opl,opr,opx,opk表示该等比数列是从opl到opr的，opl作为第一项，值为opx，比例系数为opk；
本题主要用到前缀和的原理，详见树状数组的简单运用。
还是比较基础的题，就不过多解释了~~
const maxn=1000001; var n,m,i,opx,opl,opr,opty,opk:longint; f,s:array[0..3*maxn]of int64; a:array[0..1*maxn]of int64; ch:integer; ans:int64; function pow(x,n:longint):longint; begin if n=0 then exit(1); pow:=pow(x,n div 2); pow:=pow*pow; if n mod 2=1 then pow:=pow*x; end; function ff(a1,q,n:longint):longint; begin ff:=a1*trunc((1-pow(q,n))/(1-q)) end; procedure build(x,l,r:longint); var m:longint; begin if l=r then begin f[x]:=a[l]; exit; end; m:=(l+r)>>1; build(2*x,l,m); build(2*x+1,m+1,r); f[x]:=f[2*x]+f[2*x+1]; end; procedure down(x,l,r,m,lson,rson:longint); begin s[lson]:=s[lson]+s[x]; s[rson]:=s[rson]+s[x]; f[lson]:=f[lson]+ff(s[x],opk,m)-ff(s[x],opk,l-1); f[rson]:=f[rson]+ff(s[x],opk,r)-ff(s[x],opk,m); s[x]:=0; end; procedure calc(x,l,r:longint); var m:longint; begin if (opl<=l)and(opr>=r) then begin case ch of 1:begin s[x]:=s[x]+opx; f[x]:=f[x]+ff(opx,opk,r-opl+1)-ff(opx,opk,l-opl); end; 2:ans:=ans+f[x]; end; exit; end; m:=(l+r)>>1; down(x,l,r,m,2*x,2*x+1); if opl<=m then calc(2*x,l,m); if opr>m then calc(2*x+1,m+1,r); if ch=1 then f[x]:=f[2*x]+f[2*x+1]; writeln('f[',x,']=',f[x]) ; end; begin readln(n); for i:=1 to n do read(a[i]); build(1,1,n); writeln('1=add'); writeln('2=query'); readln(m); for i:=1 to m do begin read(ch,opl,opr); case ch of 1:begin readln(opx,opk);calc(1,1,n); end; 2:begin readln; ans:=0; calc(1,1,n); writeln(ans); end; end; end; end.