我 根 本 不 会 线 段 树|线段树再学习笔记

# 我 根 本 不 会 线 段 树|线段树再学习笔记 rt。。先发出来防止咕咕咕.... 似乎是好长时间来第一次更博客。。。因为我都 没 写 完.... ---------------------- ## 一些原理方面的。。。 ### 关于线段树标记的合并与永久化 写完了写完了快写完了。 感谢曹老师教我 能打标记，那么**标记在时间轴上是有结合律的**。 如果要支持**标记永久化**，那在时间轴是还需要**具有交换律。** 比如区间加，显然可以轻松标记永久化。 但区间加，历史最值这个标记，即(add,mnd)分别表示加法标记，和历史最小加法标记。 这个东西在时间轴上可以合并，即**有结合律**：假设先进行了$(add_0,mnd_0)$，又进行了$(add_1,mnd_1)$，那最终标记就是$(add_0+add_1,\min(mnd_0,add_0+mnd_1))$。 显然这个东西是**没有交换律**的。（加的顺序肯定对历史最值有影响，从柿子上也能看出0和1并不对称。。。 所以这个标记可以打，但是不能永久化。所以树套树是彻底没救的。 ------------- 考虑一般线段树打标记，当color一个rt时，我们会把它祖先所有标记都push_down下来（祖先节点标记都为空了），再打上一个新的标记，这就体现了时间的先后性。相当于把祖先的标记（用结合律）打到它身上，再把新的标记（用结合律）也打到它身上。 而标记永久化，我们是从上到下把所有标记合并。这就根本没体现时间先后顺序，所以必须要满足交换律才行。 --------------- update：感谢tyy的教育： **不一定要真的有交换律，即$A*B$等价于$B*A$** **只需要对于一个A，你能找到一个$A'$，使得$A*B=B*A'$就可以了！**（A是时间轴上靠后的标记，按线段树的认识，靠上的标记是新打的；但是标记永久化，你不能push_down，所以你不得不把A标记打在B下面，所以就需要变成A'） 比如乘加标记，这个是不可交换的（$a_2(a_1x+b_1)+b_2!=a_1(a_2x+b_2)+b_1$，但还是可以标记永久化。 只需要modify的时候，每遇到一个标记，就乘一下乘法标记的逆元之类的就可以了、 SDOI2019快速查询不就是这样的嘛。 ----------- ### 所以线段树题，是否只需要考虑： - 当一个区间**整体**打上一个**标记**时，维护的**值**是否知道怎么变化（如果不是整体，交给push_up算维护的值） - 当一个区间**整体**打上一个**标记**时，是否知道原来标记和新来的标记怎么合并出新的标记。 - 是否能push_up。 比如众所周知的区间整除，区间加法线段树，这个标记是可以合并的： $\lfloor \frac{(x+a)}{b}\rfloor +c$ 如果维护的是最大值，我们知道“维护的**值**”会发生什么变化——大小关系不变。 但如果维护的是和，那就做不了了， 这里不能做的原因不是标记不能合并，而是不知道“维护的**值**”会发生什么变化。 ## 不熟悉的tag打法 ### CF997E：区间加，单点改，“最小值个数”的历史和 写完了写完了快写完了。 我们是对啥做历史和？是最小值个数 自然想到维护两个tag：$(cnt_i,x_i)$，分别表示历史和要加几倍当前最小值个数。以及区间要加上几。 而我们维护的值则是“区间最小值$mn$，区间最小值个数$tm$，区间历史和。” 根据我们这两天思考的线段树的关注点。只需要关注出现了一个标记，对“维护的值”的影响，以及两个标记之间怎么合并。 发现好处是，这两个标记基本上没啥关系！因为区间加是不改变最小值个数的！ “维护的值”的变化：$mn+=x_i,tm=tm,ans+=f*tm$。 标记的合并：$(cnt_0,x_0)\times(cnt_1,x_1)=(cnt_0+cnt_1,x_0+x_1)$，就没啥困难的其实。 tm只会在push_up的时候变。 细节是， **push_down的时候需要像线段树3那样，只有左（右）儿子的最小值是整个区间的最小值时，才把$f_i$的tagpush给它。** ### 区间加c，区间对x取max。单点值，单点历史最大值（UOJ164 没有历史最大值？ 在曹队教导之后，我们或许会想见，这个标记是可以合并的： 设$(v,c)$，表示x先加v，再和c取max。 考虑原标记0和新标记1该怎么合并？ $x=\max(\max(x+v_0,c_0)+v_1,c_1)=\max(x+v_0+v_1,\max(c_0+v_1,c_1))$ 于是$(v_0,c_0)\times(v_1,c_1)=(v_0+v_1,\max(c_0+v_1,c_1))$ 好处就在于max套max是可以拆的。 ------------ 再考虑历史最大值。 就考虑两个标记，x的历史最大值应该等于啥？ 应该等于$\max(x,\max(x+v_0,c_0),\max(x+v_0+v_1,\max(c_0+v_1,c_1) )) $ $=\max(x+\max(v_0,v_0+v_1...),\max(c_0,c_0+v_1),c_1))$ 如果是三个的话，就是： $=\max(x+\max(0,v_0,v_0+v_1,v_0+v_1+v_2...)\ ,c_0+\max(0,v_1,v_1+v_2)\ ,c_1+\max(0,v_2)\ ,c_2)$ 然后推一推可能就能发现了。。吧？ 就感觉好处还是max套max是**可以拆**的。都取max就很好，就都拆开，反正不会错。 所以c和v**分别维护**历史最大值就可以。。脑子不太清醒我，。反正用v更新c的时候也想要最大的。。 大概也是用先的历史最大，以及先的当前+后的历史最大，来更新总的历史。和线段树3类似的。 所以教训就是，遇到不会打的标记，不妨先推两三项感受一下。。。 关键代码： ```cpp hc[rt].v=max(hc[rt].v,col[rt].v+hf.v); hc[rt].c=max(hc[rt].c,max(col[rt].c+hf.v,hf.c)); col[rt].v=col[rt].v+f.v; col[rt].c=max(col[rt].c+f.v,f.c); ``` (是不是区间最大值/历史最大值也能做？？？) 补：这实际上和线段树3，唯一的区别在于，这个历史最值和最值操作是同向的，都是最大值；而线段树3是反向的。一个取min一个问最大值，就不得不对数域进行划分。 -------------------- ### 区间取min，询问某个点被取min的次数（UOJ#515. 【UR #19】前进四|YBTOJ 771. 「分块算法」历史序列） 这个分块我很不会啊。。。好神的。把修改挂在块上。因为是单点询问，所以每次扫一遍整个块和它上面所有修改。。push_down的时候再维护值。有点平衡复杂度的意思。 如果线段树的话，没法直接打标记。必须划分数域来着。。。 ---------- ## 想搞懂 ### 0/1异或，历史和 没写呢没写呢不要咕。 ### 不完全版的wyz第二线段树 感谢tyy，韩老师，曹队队教我ww 资瓷：维护两个值$x_i,v_i$。两种操作： - 给定F，区间执行$x_i+=F*v_i$ - 对$v_i$区间加。 - 单点询问$x_i$。（感觉问区间和也可以的。。没细想。。 口胡的做法：考虑tag：$(c,f)$，表示$x_i+=c*v_i$，**然后**，$v_i+=f$ 考虑标记的合并。只需要考虑原来有个标记$(c_0,f_0)$，然后又来了一个标记$(c_1,f_1)$，那它应该是啥样的呢？ $v_i$显然加上$f_0+f_1$就对了。 x_i应该加上$x_i+=c_0v_0+c_1(v_0+f_1)$，即$x_i+=(c_0+c_1)v_0+c_1f_1$。 所以发现，我们只需要再额外维护一个$add_i$标记，表示$x_i$额外加上一个$add_i$标记，似乎就能合并了？？ $(c_0,f_0,add_0)\times (c_1,f_1,add_1)\rightarrow (c_0+c_1,f_0+f_1,add_0+add_1+c_1f_1)$。。纯属口胡，概不负责（回头拍一下试试。。） 韩老师把这个做法叫做维护一次函数：$f$即斜率k，$add$即截距b。 update：确实可以，区间和也确实能做。快去做yt2soj目的论！！（bushi -------------- 如果对v的操作是区间赋值？？？ 似乎真的没办法通过打tag来做了。。。因为没法通过add标记来不救了。因为区间内v变化的delta是不同的。 似乎可以经典均摊的想法，维护极长联通块。变区间赋值为若干次区间加法。均摊复杂度大概是正确滴。。。 困死啦！！！！！睡大觉了！！！！ ## 其他不熟悉的一些操作： ### 二维线段树维护矩形加，矩形求 写完了写完了快写完了。 似乎要用类似hdu 5756的做法？ 假设操作是$[L_x,R_x]$，$[L_y,R_y]$的矩形加。 修改的时候，如果能完全覆盖，那就打tag 如果不能，就把内层线段树$[L_y,R_y]$区间加上交集大小倍的修改量就行了好像。 查询的时候就在第一维的log个点的内层线段树上分别查就行了。 ---------- ## 楼房重建|[[CodeForces 671E\]Organizing a Race](https://www.luogu.com.cn/problem/CF671E)|Day11T3一类问题学习笔记 写完了写完了快写完了。 ## 参考：[兔队的博客Orzzzzz](https://www.cnblogs.com/PinkRabbit/p/Segment-Tree-and-Prefix-Maximums.html) 楼房重建的问题是“前缀最大值个数” 这类问题的特点是：区间$[L,R]$的答案，会受到$[1,L-1]$传来的影响。_就楼房重建而言，这个影响即$[1,L-1]$的最大值。_ 做法是，线段树上每个区间$[L,R]$，维护不考虑$[1,L-1]$的影响的答案，同时，维护$[L,R]$这个区间对它右边的区间（[R,?]）的影响。这样根节点的答案就是全局的答案了。 问题在于，push_up的时候，不能“简单地”由左右区间的答案合并得到大区间的答案。_楼房重建中，大区间的前缀最大值个数不等于左区间的个数+右区间的个数。_ 想想我们需要的是什么：是右区间$[mid+1,R]$在受到左区间（$[l,mid]$）影响下（这个影响已经在左区间维护出了），它的答案是什么。 我们考虑在线段树上对$[mid+1,r]$递归求解。如果我们足够幸运（如果能用楼房重建的方法做），我们每次只需要递归一边。 以楼房重建为例，我们想算一个区间$[l,r]$(实际上是上面的$[mid+1,r]$)在受到“左边的最大值是mx”这个影响之下，它的答案是什么。 - 如果$mx$大于等于左儿子的最大值，那么左儿子的贡献为0，这样显然只需要递归右区间。 - 如果mx小于左儿子的最大值，那么递归算左儿子的值，右儿子的贡献就是“右儿子在受到“左儿子最大值”这个影响下的贡献”。这不就是$[l,r]$的答案减去$[l,mid]$的答案嘛！（总区间的答案本就是“左儿子的答案”“加上”“右儿子在仅收到左儿子限制下的答案”，而“右儿子在仅收到左儿子限制下的答案”正是我们需要的。 注意到上面的“加上”二字加了引号。我们能做减法是因为（“左儿子的答案”）和（“右儿子在仅收到左儿子限制下的答案”）的合并（楼房重建即加法）是具有**可减性**的。 在更一般的问题下，合并不一定具有可减性。但没关系，我们只需要对于每个节点，额外维护一个值，表示“右儿子在仅受到左儿子限制下的答案”即可！ 其实，我们楼房重建的递归，不就是在算这个值嘛！只不过我们楼房重建不用记，但如果不可减就要记。 记了这个值，说不定就不需要记录整个区间的答案了hh。回答询问的时候，就递归（和push_up一样）算一算就行啦！（就考虑最左边有一个虚空の区间，它的最大值是0hhh） -------------- 我感觉楼房重建真的阔以做区间询问啊。。。 ---------------------------------  至于这个题，我们要维护区间$c_i$的最小值（来进行线段树二分）。 类似，$[L,R]$的答案会受$[1,L-1]$里最小值的影响。 push_up的时候，需要算$[mid+,r]$在$mx[l,mid]$的影响下的答案。 这时，就需要用上面的方法， 维护一个$ans[rt]$，表示“右儿子在仅收到左儿子限制下的答案”。  至于线段树二分的部分，比较奇怪啊。 因为你要利用你维护的东西，是“只考虑左儿子的限制下，右儿子的答案”。别忘了你**二分的过程中**，也会带来一个来自它左边的区间们的限制pre。 - 当$pre\leq mx[Ls]$时，右儿子不受限制，那就能直接得到右儿子$c_i$的真实最大值，然后就能判断该递归到哪里。 - 否则，不知道右儿子的真实最大值，所以**先尝试向右区间递归**。这时，你不知道是否真的能找到。如果找不到的话，就再尝试向左枚举。这时，左区间已经完全被pre控制了，就和b无关了，直接找$a_i+pre\leq K$的第一个位置即可，是一个“正常的线段树二分”。（按我的理解：），但你左边也不能确定一定能找到解（毕竟如果这个节点的父亲是这种“尝试向右递归的情况”走到的它，你不能确定这个区间一定有解。）所以这个复杂度$n\log ^2n$。 **二分的过程中**，会带来一个来自它左边的区间们的限制pre。 ----------- - 试试楼房重建是否能做区间询问。 似乎（据tyy说）是可以的。 -------- 而今天的题目，有点不一样，但也有点类似。。 思想似乎是，整个区间维护的信息，不足以支持你回答问题。所有要递归到子区间（利用更加详细的信息）来回答。如果我们足够幸运，就只需要递归到一个区间来求。 上面的题是因为“左边传来的影响”，使得不能直接回答，而要递归下去。这个题似乎是因为，为了避免出现两个栈的底被冲破的情况发生（一旦发生，根本不知道该取哪儿），所以不能直接回答，要递归下去。 哎。。但好像这么解释也不太好啊。。。它似乎是，一旦出现被冲破的情况，那一定会递归到右边。可是递归到右边，那就不用处理这个冲破的情况了啊？？？ -------- 似乎这种思路可以做一些看起来很难支持某些操作的问题。比如昨天(Day11)T3和楼房修建，看上去权值增大比较容易，权值缩小巨大困难。（实际上可以通过维护的儿子信息，用楼房重建的push_up来得到）。当时还考虑线段树分治了。 ------------- 似乎题解的做法非常的神奇？好像是分别考虑取较晚的一个？