menu zcmimi's blog

arrow_back 平衡树

可以考虑把字符串倒序

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

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

zc
2020-05-29 17:09

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

GSS1,GSS3: 最大子段和:

每个节点记录区间和,最大后缀和,最大前缀和,答案

```cpp node operator+(node x,no

zcmimi
2020-05-25 19:22

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

include<bits/stdc++.h>

pragma GCC optimize(3)

de

zc
2020-01-22 09:44

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

接着我们枚举删掉哪个点

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

删掉这个

zc
2019-12-31 11:31

fhq treap or splay

记录区间最小值

直接模拟即可 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GC
zc
2019-12-21 19:47

```cpp

include<bits/stdc++.h>

include<ext/pb_ds/assoc_container.hpp>

include<ext/pb_ds/tree_polic

zc
2019-12-21 19:47

Robotic-Sort top: 0


同排序机械臂 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimi
zc
2019-12-21 19:47

学习的原因:

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

1. 短

2. 好理解、好记

3. 应用范围广

不过学之前还是先对treap原

zcmimi
2018-12-29 22:31:53

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

最短(最简洁)代码:

``` 解释: turn(x,p): 将x的左(p=0)/右(p=1)儿子旋转到x的

zcmimi
2018-12-01 21:10:58
1 / 1
Search
search