线段树出了名的操作是lazy标记。
普通lazy标记涉及到pushup和pushdown
这个pushup只涉及两个儿子合并，并且两个儿子是两个点。
但是有的时候，两个儿子是两个树，pushup复杂度就爆炸了。
给你一个线段树的树套树，外层的线段树pushup一下，就对应里面每个节点对应pushup。O(n^2log^2n)优秀数据结构诞生辣
还有的时候，主席树要区间修改。
每次修改操作我们在之前基础上建一棵新树，问题是，儿子是共用的，pushdown一下，之前的版本也会受到影响。凉凉。
所以要标记永久化。
标记永久化，就是标记不用pushdown，自然也不用pushup（开始建树的时候，可能要pushup）
以一维线段树区间加，区间求和为例。
add懒标记，sum是和。
upda时候，路上的sum都加上c*len；如果到了该返回的完全包含节点时候，再把add加上c。
query的时候，把路上的add都做和，到了该返回的节点的时候，返回sum[x]+addsum*len（注意这一层的add别加了就）
可以发现，一路统计，一路标记下来，add，sum有机配合，就可以算出了。
可以理解为，query的时候，在x节点的父亲做过的赋值用add求了出来，x子孙做过的赋值sum已经处理完毕。所以没有问题。
真正的例子：
[POI2006]TET-Tetris 3D
二维线段树，矩形求max，矩形取max
（ps：这个题不是矩形取max的话，如果是矩形赋值，标记永久化还真做不了。。）
外层行，内层列。
对于外层的线段树，这个是不能懒标记的。
类比上面开两个变量，这里我们开两个树。
一个mx树，节点上的内层线段树记录这若干行压缩起来的最大值
一个tag树，节点上。。。。。。。。。。。。所打标记的最大值
然后update，query类比即可 。
内层线段树由于儿子就是两个点，所以随意了。
代码：（空间玄学，反正卡着边界能过）
#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') #define mid ((l+r)>>1) using namespace std; typedef long long ll; il void rd(int &x){ char ch;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=1050; int n,m,k; struct node{ int ans[2*N],laz[2*N]; void upda(int x,int l,int r,int L,int R,int c){ ans[x]=max(ans[x],c); if(L<=l&&r<=R) { laz[x]=max(laz[x],c);return; } if(L<=mid) upda(x<<1,l,mid,L,R,c); if(mid<R) upda(x<<1|1,mid+1,r,L,R,c); } int query(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ return ans[x]; } int ret=laz[x]; if(L<=mid) ret=max(ret,query(x<<1,l,mid,L,R)); if(mid<R) ret=max(ret,query(x<<1|1,mid+1,r,L,R)); return ret; } }mx[2*N],tag[2*N]; void upda(int x,int l,int r,int l1,int r1,int l2,int r2,int c){ mx[x].upda(1,1,m,l2,r2,c); if(l1<=l&&r<=r1){ tag[x].upda(1,1,m,l2,r2,c);return; } if(l1<=mid) upda(x<<1,l,mid,l1,r1,l2,r2,c); if(mid<r1) upda(x<<1|1,mid+1,r,l1,r1,l2,r2,c); } int query(int x,int l,int r,int l1,int r1,int l2,int r2){ if(l1<=l&&r<=r1) return mx[x].query(1,1,m,l2,r2); int ret=tag[x].query(1,1,m,l2,r2); if(l1<=mid) ret=max(ret,query(x<<1,l,mid,l1,r1,l2,r2)); if(mid<r1) ret=max(ret,query(x<<1|1,mid+1,r,l1,r1,l2,r2)); return ret; } int main(){ rd(n);rd(m);rd(k); int x,y,s,d,h; while(k--){ rd(d);rd(s);rd(h);rd(x);rd(y); ++x,++y; int ch=query(1,1,n,x,x+d-1,y,y+s-1)+h; upda(1,1,n,x,x+d-1,y,y+s-1,ch); } printf("%d",query(1,1,n,1,n,1,m)); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/9 18:33:23 */
ps：感觉如果值不具有覆盖性（取max）或者等价撤销性（加减），就不能标记永久化了（赋值）