【BJWC2018】Border 的四种求法

线段树合并的空间常数太大了，有些时候会被卡掉，这里提供一种空间常数较小的做法。 我们可以先将询问按$r$递减排序，然后扫过去，每次处理之前加进去的询问，看当前位置是否能被作为$i$，然后把已经处理完毕的询问给删掉，再加入当前询问。现在的问题还是在处理询问，发现其实可以对于每一条链打一个$l$的标记在最深的地方，处理询问就查一下$i$到根的最大$mxlen(x)+l$，然后删掉询问。加入询问就是沿着重链往上跳，放标记。具体实现上，查询最大值是线段树可以做的事情，然后你需要对于每个结点开个$set$记录这个结点还有哪些标记，查询的时候讨论一下标记的位置即可。 这样空间常数较小，大概是线段树合并的$\frac{1}{2}$甚至更小。因为这里线段树不用多开$log$的空间，空间上的瓶颈是在$set$上，而询问是动态加减的，很多数据下可能当时存在在$set$里的标记就没几个。