线段树出了名的操作是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已经处理完毕。所以没有问题。

 

真正的例子：

二维线段树，矩形求max，矩形取max

（ps：这个题不是矩形取max的话，如果是矩形赋值，标记永久化还真做不了。。）

外层行，内层列。

对于外层的线段树，这个是不能懒标记的。

类比上面开两个变量，这里我们开两个树。

一个mx树，节点上的内层线段树记录这若干行压缩起来的最大值

一个tag树，节点上。。。。。。。。。。。。所打标记的最大值

然后update，query类比即可 。

 

内层线段树由于儿子就是两个点，所以随意了。

 

代码：（空间玄学，反正卡着边界能过）

#include
     
      #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
     

 ps：感觉如果值不具有覆盖性（取max）或者等价撤销性（加减），就不能标记永久化了（赋值）