OceanEye's Blog

是时候表演真正的技术了!

@OceanEye2周前

08/9
11:04
OI 模板——如果有哪里不对的请打死我

替罪羊树【复习向】

这是新坑……
同时开了KDT和LCT的坑【不知道的同学等下就知道了】

0x00

绝大多数的平衡树维持平衡是通过旋转操作
Merge_Split_Treap 是通过分裂合并维护堆的性质保持理论上的平衡
今天讲的替罪羊树是用来暴力维护子节点重量平衡的

0x01

某教程的传送门
另一个教程的传送门
这两个教程里面的说明都很有意思,可以看看

0x02

替罪羊树最神奇的地方就在于他的暴力重建
而且这个暴力重建是有时间复杂度保证的【势能分析那一套理论不是很懂,需要证明的可以去翻翻之前陈老师的论文】
保证每种平衡树的操作的时间复杂度在\(O(logN)\)的范围

替罪羊树还有一个小技巧
就是拍扁重建法
重建的时候先dfs把所有数放进一个数组,重建每一层递归都把mid拿出来当father即可
时间复杂度是O(size)的

最后讲的是替罪羊树的删除
因为这个树是没有旋转的
不能把它某个节点旋转到叶子然后把叶子节点删掉
所以用的是惰性删除
在删除的时候 打一个删除标记 表示“这个点被删除了 以后查询的时候直接跳过”
若一个子树内的惰性节点超出了某个范围【比如\(size*0.45\)】直接暴力重建

注意:
重建的时候带有删除标记的节点不能入数组
重建的两个条件
1.子树深度大于某个阈值 或 子树大小大于阈值 【实际上是等价的?】
2.子树内带有删除标记的节点大于阈值

0x03

代码
这份过了编译【就是不保证完全正确但是思路是对的】
状态好了来认真写一份……

替罪羊树【复习向】

@OceanEye2周前

08/8
21:55
OI

Link Cut Tree 学习笔记

先上一份代码……回去研究研究 @Sdchr

 

Link Cut Tree 学习笔记

@OceanEye2周前

08/6
21:44
OI

后缀数组学习笔记

学习地址的传送门
当然要看我的也是资瓷哒qwq

0x00

前置知识
SA是所有的后缀的排名
\(sa[i] = the i^{th} suffix’s position \)
rank是某后缀对应在SA中的位置
\(rank[i]= find_pos(sa.begin(),sa.end(),i) \)
height是求完SA之后 相邻排名的后缀 最长公共前缀的长度
\(height[i]= lcp( suffix[i] , suffix[sa[rank[i]-1]]) \)

个人认为最难理解的就是双关键字的桶排序……【其实还算好理解?】
menci大佬的实现是先把第二关键字整理成有序的
\( tmp[len- –buc[sec[i]]] = i \)
操作之后tmp就是按照第二关键字排序的一个数组
接下来把第一关键字占的位数存进桶里面
再用tmp这个第二关键字的有序队列 【这个队列是倒着的 是倒着的 是倒着的】
结合第一关键字的桶 可以推出新的SA
最后用SA数组来推出新的rank数组
\(
if(last==empty) rank[sa[i]]=1
\)
如果是第一个那么rank必定为1
\(
if(last->fir==i->fir /and last->sec==i->sec) rank[sa[i]]=rank[last]
\)
如果第一第二关键字都相同那么排名相同
\(
rank[sa[i]]=rank[last]+1
\)
否则依照SA顺序名次+1
//更新last

建议看第二个模板
模板没有注释
需要完整的解释……请跳转至menci的博客【传送门在上面】

没有height只有sa和rank的

 

这个是有height,sa和rank的

后缀数组学习笔记

@OceanEye3月前

05/26
14:55
OI

BZOJ2730

XDDD YY了半天的点双联通忽略了最初点双的性质—-割点可能属于多个块

点双学习Link 1 2 3

代码施工中

BZOJ2730

@OceanEye3月前

05/24
13:18
OI

BZOJ2982

Lucas定理裸题

恩具体证明请百度 Lucas定理

刚刚发现我是RK3 :-D高兴

 

 

BZOJ2982

@OceanEye3月前

05/21
13:46
OI

FFT—-学习笔记

先上几个好的教程

  1. 某不知名大佬的教程 简直良心治好了我一直没搞清楚的FFT:-D
  2. zky大佬的FFT教程 
  3. kry大佬的板子:-D

[手动分割]

 

UOJ34—-多项式乘法

 

BZOJ2179

 

BZOJ2194

好像就是反过来?

挺裸的:-D

 

 

[代码施工中]

FFT—-学习笔记

@OceanEye4月前

04/8
00:03
OI

BZOJ1834

嘛……几万年没好好写过网络流了……
gap优化真的强,把我的1s的代码降成了0.05s
相信前面榜上的就是gap的吧……

BZOJ1834