网络文化经营许可证申请,百度快照如何优化,app开发经费预算表,建筑培训网首页安全员Count on a Treap
题目来源
Codechef Feb 2014 COT5 https://www.codechef.com/problems/COT5
问题提出
什么是Treap
是一颗二叉搜索树,每个节点拥有keykeykey属性.是一颗堆,每个节点拥有weightweightweight属性
问题 nnn次操作,三种类型,要求维护大根Treap …Count on a Treap
题目来源
Codechef Feb 2014 COT5 https://www.codechef.com/problems/COT5
问题提出
什么是Treap
是一颗二叉搜索树,每个节点拥有keykeykey属性.是一颗堆,每个节点拥有weightweightweight属性
问题
nnn次操作,三种类型,要求维护大根Treap (0,k,w)(0,k,w)(0,k,w) ,插入keykeykey为k,weightk,weightk,weight为www的点.(1,k)(1,k)(1,k),删除keykeykey为kkk的点(2,ku,kv)(2,k_u,k_v)(2,ku,kv),询问keykeykey为ku,kvk_u,k_vku,kv的两点在TreapTreapTreap中的距离.
保证keykeykey,weightweightweight均不相同.
问题解答
dist(u,v)dep(u)dep(v)−2∗dep(lca)dist(u,v) dep(u) dep(v) - 2* dep(lca)dist(u,v)dep(u)dep(v)−2∗dep(lca)
我们以keykeykey为下标,将这个树按中序遍历展开.
显然[ku,kv][k_u,k_v][ku,kv]之间最大的weightweightweight最大的点就是两点的lcalcalca.
证明:首先lcalcalca一定在区间[ku,kv][k_u,k_v][ku,kv]之间,不然ku,kvk_u,k_vku,kv将位于lcalcalca的同一侧,这不可能.其次权重最大的点一定是这颗子树的根节点,这个点一定是祖先,如果它不是lcalcalca的话,那么它的keykeykey将大于或小于lcalcalca形成的子树中所有的点的keykeykey,也就是说它不在区间[ku,kv][k_u,k_v][ku,kv]之间,矛盾.
至此,用线段树可以轻松维护lcalcalca.
那么如何维护一个点在树上的深度呢?
根据Treap的特殊性质,我们知道每个点的weightweightweight一定小于他父亲的weightweightweight.
从这个点到根节点的祖先链上的weightweightweight是不断递增的.
这里有一个非常特殊的性质,在序列上就是从这个点往两侧各找一个直接的递增子序列,那么序列上的点都是他的祖先.
这个性质基于这样一个事实:每个点左右两侧的第一个大于它weightweightweight的点,都是这个点的一个祖先.因为其中一个点是它的父亲,而另一个点…自己画图观察一下就好了.
因此两个递增序列的长度和就是它到根的距离.
如何维护某一个点向右的直接递增序列呢.也是使用线段树,参考我的另一篇博客,楼房重建.
