Statement
树,给 \(m\) 条带权路径 \((a,b,v)\),\(q\) 次询问包含 \((u,v)\) 的路径中的第 \(k\) 小权值.
Solution
好题!这篇题解延伸出了很多东西。
首先路径的包含关系转为矩形(二维限制关系)是比较显然的.
具体地,\((u,v)\) 包含 \((a,b)\) 有两种情况:
- \(u,v\) 无祖先关系:\(a\) 在 \(u\) 子树内,且 \(b\) 在 \(v\) 子树内,写出来就是 \(\text{dfn}(u)\le\text{dfn}(a)\le\text{dfn}(u)+\text{siz}(u)-1\) 且 \(\text{dfn}(v)\le\text{dfn}(b)\le\text{dfn}(v)+\text{siz}(v)-1\).
- \(u,v\) 有祖先关系:设 \(u\) 为 \(v\) 祖先,\(w\) 为 \(u\to v\) 路径上的第二个点(\(u\) 向 \(v\) 方向的第一个儿子),则有 \(a\) 在 \(v\) 子树内,且 \(b\) 在 \(w\) 子树外,写出来:\(\text{dfn}(v)\le\text{dfn}(a)\le\text{dfn}(v)+\text{siz}(v)-1\) 且 \(1\le\text{dfn}(b)\le\text{dfn}(w)-1\) 或 \(\text{dfn}(w)+\text{siz}(w)\le\text{dfn}(b)\le n\).
注意到这样的 \((a,b)\) 的取值范围就是矩形,第二种情况是两个矩形,然后这是一步转化.
然后现在是 \((u,v)\) 被包含,也即问题变成了求包含一个点的权值第 \(k\) 小矩形.
这怎么做呢,一种显然的方法是整体二分:一次二分 \(x\) 就把所有权值 \(\le x\) 的矩形加入,判断这个点被包含了多少次.
那如果我把题改成强制在线怎么办呢!!!
先不考虑强制在线,我们可以把每个询问点离线下来排序,问题变成了需要支持区间插入一个数、区间删除一个数、单点查第 \(k\) 大.
一看就很树套树,那假装我们使用外层线段树、内层平衡树,考虑标记永久化,发现是三 log 的.
具体地,对于区间插入,我们找到外层线段树上 \(\log\) 个点,对这 \(\log\) 个点进行插入,删除类似. 这样他们儿子没有应用到这些更新,怎么办呢,你查一个叶子时,找出它以及它的所有 \(\log\) 个祖先,对这 \(\log\) 棵平衡树求他们并起来的第 k 大.
众所周知,这只能最外层二分、用排名之和判定来做(二逼平衡树),这样修改是双 log、查一次是三只 log 的,甚至不如整体二分!!!
怎么办呢,我们发现问题在于多棵平衡树无法一起二分,那我们改成外层线段树、内层权值线段树.
这样,还是同样地标记永久化,对于区间插入,对内层 \(\log\) 棵权值线段树进行单点加,区间删除类似;对于单点查,我们同样地拎出根到叶子路径上 \(\log\) 棵权值线段树,发现这时就可以多棵权值线段树一起二分了,复杂度降为双 log.(也可参考二逼平衡树的多种做法的对比)
这样我们就做完了离线问题,那强制在线怎么办呢?
发现直接持久化一下就行了,(可持久化树套树,参考 bzoj3489),时间并未增加,空间升为双 log.
具体怎么做呢,假如我们已经可以持久化了,那我们把扫描线的过程持久下来,在线询问直接在对应版本询问即可;
发现外层持久化是容易的(只维护内层线段树的根),而外层复制一次节点,内层线段树肯定不能全部复制,发现因为是单点修改,还是只复制发生更改的节点即可,然后做完了.
那如果是区间插入、区间删除、区间查第 k 小,可以离线,怎么办呢!!!
发现外层线段树区间查询,经过的点数是 \(\log\) 级别的,然后把这些点拿出来一起二分就行了.
强制在线是一样的,复杂度都没有增加.
那我们回归到原问题,我常数太大了怎么办!!!
尝试把外层线段树改成树状数组,区间插入、删除可以转化为前缀插入、删除,单点查可以变成两段前缀相减得到的树的 kth,这同样是单 log 的.
发现这样可以扩展到区间查询.
然后树状数组理论上是可以持久化的……
当然还有其他各种做法,比如 K-D Tree,树上莫队 + 值域分块等等。
总结:一道题的价值不仅在于过掉它,更是在于要总结方法、结论、trick 和规律,完善你的思考、思维方式,更好的是你通过这道题进行延伸、温故而知新,比如想他的加强版可不可以这样做,如果不行还能怎样做,这样就可以自己出题目,可以为师矣!
标签:水果,le,log,题解,线段,区间,dfn,text,P3242 From: https://www.cnblogs.com/laijinyi/p/18309274