bzoj2770YY的Treap&&COT5

这题没有COT4那么虐人——fotile
这题卡内存才有趣——fotile

其实在noip前后的时候逛bzoj时候点进了bzoj2770……主席过来扫了一眼,表示他出的COT5就是这题的加强版。

然后主席说cot5比较简单所以就隐藏了……呵呵……

当时就被吓尿了……直接回教室自修准备期中考去了……

今天无事来看看……找了找性质发现bzoj那题也不是特别难

首先看yy的treap这题……

description

维护一个treap,每个节点有value和priority,要求treap每时每刻都满足:
按value来看是一棵二叉搜索树
按priority来看是一颗小根堆
要求支持:
给定value,priority,插入一个节点
给定v,删除value为v的节点
给定vu,vv,询问value为vu,vv两点的lca的value
保证任何时刻value和priority都两两不同

SOL

直接用lct之类的东西维护这个treap不现实……
观察性质就可以明白什么了(喂)


颓废了很久来继续更新……
首先询问的两个点的value形成了一个区间[vv,vu]
那么显然它们的lca的value一定在这个区间里面
而满足值在[vv,vu]的节点中,priority最小的
一定就是lca了
证明略
那么就变成了维护一个集合:
支持查询区间最值,加入删除元素
线段树或平衡树就可以了……


COT5

询问treap两点距离
容易发现只要能够维护treap任意一点的深度
就可以解决了……
接下来继续观察性质
就能发现维护这个也不难

Comments

comments powered by Disqus