YbtOJ 维护集合 题解

Description

你需要维护一个可重集,初始集合为空,支持 $4$ 种操作:

  • I k 向集合内插入元素 $k$。
  • A k 将集合内所有元素加上 $k$。
  • S k 将集合内所有元素减去 $k$。
  • F k 查询集合内第 $k$ 大。

你需要进行 $n$ 次操作。

一开始给出一个下界 $Minv$,表示集合内的所有元素都必须大于等于 $Minv$,在任何时刻,小于 $Minv$ 的所有元素会被立刻删除。

最后还要输出被删除的元素个数。

$1\leq n \leq 3\times 10^5,0\leq Minv\leq 10^9$

Solution

考虑用 fhq Treap 维护该可重集。

对于操作一,只需要直接插入即可。

对于操作二、三,由于是对当前集合内所有元素统一操作,所以考虑记录一个全局变量 $Sum$,表示当前集合内所有元素实际大小应该加上 $Sum$。

那么每次操作一需要注意插入的值要减去 $Sum$。

查询第 $k$ 大还是基本操作,只是最后要加上 $Sum$。

注意与 $Minv$ 的判断即可。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇