Treap
「SHOI2013」发牌-fhq Treap
· ✏️ 516 words · ☕ 2 mins read

在一些扑克游戏里,如德州扑克,发牌是有讲究的。一般称呼专业的发牌手为荷官。荷官在发牌前,先要销牌。所谓销牌,就是把当前在牌库顶的那一张牌移动到牌库底,它用来防止玩家猜牌而影响游戏。

假设一开始,荷官拿出了一副新牌,这副牌有 $N$ 张不同的牌,编号依次为 $1$ 到 $N$ 。由于是新牌,所以牌是按照顺序排好的,从牌库顶开始,依次为 $1, 2, \dots$ 直到$N$ ,$N$ 号牌在牌库底。为了发完所有的牌,荷官会进行$N$ 次发牌操作,在第 $i$ 次发牌之前,他会连续进行 $R_i$ 次销牌操作, $R_i$ 由输入给定。请问最后玩家拿到这副牌的顺序是什么样的?


「ZJOI2012」小蓝的好友-Treap
· ✏️ 1673 words · ☕ 4 mins read

简单版题意:

给定一个 $R \times C$ 的矩形,在其中 $N$ 个位置有随机生成的资源点。现在请你求出在所有的子矩形中,至少包含一个资源点的矩形数量。


「ZJOI2007」报表统计-平衡树
· ✏️ 1203 words · ☕ 3 mins read

有一个长度为 $n$ 的整数序列,并且有以下三种操作:

  • INSERT i k :在原数列的第 $i$ 个数后面添加一个新数 $k$ ;如果原数列的第 $i$ 个数已经添加了若干数,则添加在这些数的最后

  • MIN GAP:查询相邻两个数的之间差值(绝对值)的最小值

  • MIN SORT GAP:查询所有数中最接近的两个数的差值(绝对值)


「NOI2005」维护数列-非旋Treap
· ✏️ 1513 words · ☕ 4 mins read

维护一个数列,给定初始的 $n$ 个数字。

现有六种命令:

  • 在第 $pos$ 个数后插入 $tot$ 个数
  • 翻转从第 $pos$ 个数开始的 $tot$ 个数
  • 删除从第 $pos$ 个数开始的 $tot$ 个数
  • 查询从第 $pos$ 个数开始的 $tot$ 个数的和
  • 设定从第 $pos$ 个数开始的 $tot$ 个数设定为 $c$
  • 查询整个数列中和最大的连续子区间的和

非旋Treap学习笔记
· ✏️ 3050 words · ☕ 7 mins read

非旋 Treap ,是一种不基于旋转的平衡树。它基于 Treap 的树堆思想,并且能够高效的完成某些对区间的操作,而且灵活性比较高。它也可以进行可持久化的操作。


Treap学习笔记
· ✏️ 5088 words · ☕ 11 mins read
闲下来了,开始写一点学习笔记,也希望能给后人造福吧。第一篇来说一说Treap。