zcmimi's blog

arrow_back平衡树共9篇文章

avatar
zcmimi
2020-05-25 19:22:00

SPOJ的GSS系列是关于区间统计技巧的集合

非常适合锻炼码力

LG GSS1 | SPOJ GSS1

[LG GSS2](

avatar
zcmimi
2018-12-29 22:31:53

学习的原因:

之所以选择fhqtreap,不是因为可以可持久化,是因为:

1. 短

2. 好理解、好记

3. 应用范围广

不过学之前还是先对treap原理稍微有些了解比较好

其中有些细节还是要靠自己意会意会

原理:

概述:

f

avatar
zcmimi
2018-12-01 21:10:58

https://www.luogu.org/problemnew/show/P3369

最短(最简洁)代码:

解释:
turn(x,p):
    将x的左(p=0)/右(p=1)儿子旋转到x的头顶(变成x的父亲)

![](https://i.loli.net/2018/12/05/

avatar
zc
2020-05-29 17:09:00
查看原题

点击跳转

可以考虑把字符串倒序

这样添加一个字母相当于增加了一个后缀,相对原来更好处理

可以发现在插入新的字符串时,height改变的只有height[pre],height[p],height[nxt]

通过平衡树动态维护这三个位置就可以了

avatar
zc
2020-01-22 09:44:00
查看原题

点击跳转

直接模拟,把平衡树当做可以\Theta(\log n)访问并删除任意位置的链表

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

这个图是个DAG,我们可以很快地处理出每个点以他为起点(ds_i)或终点(dt_i)的最长路

接着我们枚举删掉哪个点

我们可以将拓扑序小于当前点的点称作A集合,大于的称作B集合

删掉这个点后的最长路有三种可能:

A\rightarrow A,A\rightarrow B,B\rightarrow B

(to指x连接的点)

当删除一个点x时,我们可以删去所有集合中的dt_to+1+ds_x(反向图中的)

求出集合中的最大值就是当前最长路长度

接着将dt_x+1+ds_to加入集合,转移到下一个状态(原图中的)

于是我们需要一个数据结构满足以下要求:

  1. 插入某个值
  2. 删除某个值
  3. 查找最大值

我们可以用堆(手写堆或者两个stl优先队列)、平衡树、权值线段树等维护

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

fhq treap or splay

记录区间最小值

直接模拟即可

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Robotic-Sort top: 0

同排序机械臂

1/1
Search
search