可能陆陆续续补完吧...咕咕咕
先贴一手, AcWing的全解析
完善程序
(2)（RMQ 区间最值问题）
题意描述得非常具体(嗯, 都是我当时在考场上没学的东西)
前置知识
- 笛卡尔树
- 欧拉序
- ST表
这边贴几个网址吧, 毕竟我本人也就为这个解析刚学.
搜索二叉树-百度百科
笛卡尔树-百度百科
笛卡尔树-OI-WIKI
笛卡尔树-blog
欧拉序
笛卡尔树, 就是一个每个节点有两个值, k 和 w.
其中一个(k)满足搜索二叉树的性质, 另一个(w)满足堆的性质
这道题, 是将数组下标看作k, 将val看作w.
了解了欧拉序后, 因为欧拉序有一个性质, 点x和点y的lca一定在x和y的欧拉序之间更加准确的说是x最后出现的欧拉序到y最先出现的之间.
st表是运用了倍增的思想, 可以求区间最值的数据结构
首先, 总的说一下这道题的思路, 将区间最值问题转换为LCA问题, 在用区间最值问题来求解LCA.(使用分块的思想, 预处理, 最终降低了时间复杂度)
一开始建笛卡尔树, 因为它要同时满足两个性质, 我们先按k排序(本题因为是以数组下标作为k, 不用排序, 遍历即可), 因为k要满足搜索二叉树的性质, 后加入的k一定比前加入的k的值要大, 所以插入的地方只能在根节点的右链(包含根节点)上, 否则不满足性质, 具体插在哪个位置, 是看哪个位置能够满足堆的性质, 及用w(本题的val)来比较, 若要满足堆的性质要使得当前待插入的节点变为当前根节点的父节点, 就把当前根节点作为待插入点的左儿子
更好理解插入的操作, 我提供一张配图
不难理解, 这样的操作, 一定是满足搜索二叉树的性质, 而我们插入也一定可以找到一个位置使它满足堆的性质(本题本质上是寻找右链上第一个比它小的节点位置, 实现方式为单调栈)
分析到这里建树的函数的题就可以做出来了.
1.选A.
还没找到就把当前弹出来的节点暂时任命为它的左儿子, 直到它找到第一个比它小的节点位置,
那时候while结束, 待插入节点的左儿子就定下来了.
所以这题选A.
2.选D
如果它不是变为根节点的父节点的话, 即top不为空的话, 就把它的上一个节点的右儿子变为待插入节点.
至此, 笛卡尔树的建树过程结束了.
由欧拉序的性质, 我们要查找的区间最值就转变为了求x, y的lca, dfs跑完后, 我们要求的lca显然是x,y之间的深度最小的点.
3.选A
后面的query等函数中调用min, 最后输出的那个点对应的val,
所以这里的min是用来比较各个分块后的块内的lca的最小深度.
之后判断区间内的lca其实所用的深度只要是区间内的相对深度即可,
因为相邻的点的深度只有+-1关系,我们只要预处理出来每个块内的峰值.
4.选D
由上面分析可得, Dif里存的是可能是x, y点之间的深度变化关系,
所以比较前后两个欧拉序的深度.
5.选D
mx代表最小值, 容易判断是深度的最小值.
这里是预处理出来每个块中给所有可能的+-状态, 直接预处理出来这个状态的lca的位置,
结合第四题分析, 对v进行加减操作, 若深度小于最小值就更新最小值的点.
注意: 是i-1, 要观察好前一个更新Dif的式子.
6.选C
通过后面的return值, 不难看出要求出[l, r]的lca的相对位置(后面加了偏移量l).
必须要移除l前的与r后数据, 因为求的是[l, r]的最小值.
所以先右移, 把l前的加减操作清除掉, 在和与长度为r-l+1的`11...11`做与操作就成功将[l, r]的操作取出.