「SHOI2013」发牌-fhq Treap

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

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

「ZJOI2012」小蓝的好友-Treap

简单版题意:

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

「ZJOI2007」报表统计-平衡树

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

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

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

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

「NOI2005」维护数列-非旋Treap

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

现有六种命令:

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

非旋Treap学习笔记

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

Treap学习笔记

闲下来了,开始写一点学习笔记,也希望能给后人造福吧。

第一篇来说一说Treap。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×