@[colldisSavior](/space/show?uid=7020)
不像Splay那样可能有个`cnt[]`记个数,$fhq\ treap$不需要判重,每个数都是单独的一个节点,你可以从各操作中看出来。
by SovietPower✨ @ 2018-04-04 19:48:23
@[SovietPower](/space/show?uid=39887) 似乎有些道理......是因为$\rm fhq\ treap$每次针对的是在值相同情况下下标最小的数操作的吗?
by teafrogsf @ 2018-04-04 20:34:21
@[colldisSavior](/space/show?uid=7020)
好像和下标没有关系吧,每次删除删掉最顶上那个,是对fix最小的操作。
by SovietPower✨ @ 2018-04-04 21:47:16
@[SovietPower](/space/show?uid=39887) 下标最小也就是第一个吧?不然查Rank子树会有问题
by teafrogsf @ 2018-04-05 00:56:40
@[colldisSavior](/space/show?uid=7020) Rank和下标有关系么。。不是只看值吗
by SovietPower✨ @ 2018-04-05 07:37:38
@[SovietPower](/space/show?uid=39887) 所以是每个数字单独占一个Rank?
by teafrogsf @ 2018-04-05 08:24:17
@[colldisSavior](/space/show?uid=7020) 不太理解你的意思。。如果说$Splay$中每个点占$cnt[rt]$个Rank,那$fhqTreap$是一个数字一个Rank。
by SovietPower✨ @ 2018-04-05 08:35:13
@[SovietPower](/space/show?uid=39887) 也就是说这题目是要求重复数字不叠加对吧?谢了XD
by teafrogsf @ 2018-04-05 08:48:11