UnyieldingTrilobite
2024-10-20 02:02:29
大概还是想记录一下这些吧，那些我所真正热爱的。
每个文可能（理论上）有很多个标签，会选择一个比较合适的归类进去。
特别置顶：
【详细介绍】一种基于斜二进制的序列&树上数据结构
线段树，阿克曼，分块
拜线段树教：https://www.luogu.com.cn/team/55190。
其实还有更早的但被这篇子集了。大概是想写点什么，虽然写的确实很烂。
第一次在 UOJ 上写文。东西确实没啥用，但这个思路被 ut 记下了。
上面那篇的后续。当时感觉好 NB，然后就被怒斥了，并从某位大佬处学到了
对非递归线段树的再次思考，囿于“树”形态的桎梏，造出了这样一个奇奇怪怪的东西。发出后，从某位大佬处学到了 CF 上那个进化成森林的线段树。
进化到脱离线段树范畴的非递归写法。实际胡的时间比上面那篇早，但是写锅重置了。
什么罐头我说，男人。另外这篇也是有前置的，在后面。
非递归高光时刻。
2020 年上半 ut 就尝试过用 zkw 线段树救爷爷，未遂，主要原因是
其实是个线性空间的动态开点 BIT。这东西是有前置的，后面会提。
比压缩 Trie 好写。
基于线段树的精细化多层分块实现。
如何优雅地在 zkw 线段树上跑无修 rmq 【笔记】和一种野蛮处理静态序列多次在线区间查询的数据结构的后续。事实上在此一年前 ut 已经把这套思路搞到了在线的单
上面那篇的上树版。
上上面那篇的在线版说不定到时候也给上个树排列组合。
理论最优！！1
由于各种原因 ut 在很长一段时间里玩不明白左偏树，然后初见配对堆的时候惊为天人。
书接上文，ut 初见斜堆。
书接上文，ut 在论文里初见 hollow heap，Tarjan 老爷子的代码还写挂了。
同样是 Tarjan 论文里挖出来的。
斐波那契堆。
好玩，爱玩。
是哪篇的后续我不说。
斜堆后续。
配对堆后续，补了一个比较劣的复杂度证明。
二项堆，懒二项堆，斐波那契堆。
关于文章里提到的某个名字……初见端倪？
很有启发性的一个堆。纠结了很久要不要把这个丢到最上面那个分类。
上面某篇的复杂度证明。
如果有人试图对着实现代码就会发现，写得真的很烂。
姗姗来迟的 OI 快乐堆。
不知道为什么比较冷门，可能大家都不是很缺这点 MST 性能？
糖人糖码和后面某个东西共同的核心前置。姑且还是归到堆里比较好。
【娱乐向】战术 priority queue 的咆哮正统后续。
之所以这里另外只有一篇是因为大部分都被收进上面那个文里了。这篇也是被子集的。
在得到指正后，ut 和朋友一起去改了 OI-wiki。
不会点分树导致的。
非常冷门的算法，基本没啥用。
万恶之源。
初见端倪。
渐入佳境。
大彻大悟。
self-adjusting 的含金量。
感觉不如融合树。
即使不是路径压缩，复杂度也可以是对的。
联想一则。
其实没有线段树救爷爷。那么重量级。
模型失真比较严重，实际意义有限。这个系列旨在用三篇论文来说明随机数据的路压并查集复杂度是线性的。但这篇其实不需要路压。
其实有（中）但还没写好……另外这篇的逻辑是真的很奇怪。
奇怪的不知道为啥没加入标准的随机数函数。
省流：##define private public。
就是说您老的这个库和命名空间能不能搞得稍微阳间一点后续。
由于一般通信题不会这么唐，实际上除了让你的代码变得特别神秘以外没啥用。
那怎么还真有这么唐的通信题还不开 O2。
省流：函数套函数。好玩起见叠了个厌氧菌。
如何遍历一个 std::stack（详细揭秘）的后续。
在洛谷写了不少东西但全都被这篇子集了。
刚打完 NOI 闲的没事干导致的。
后续。
还是后续。实际上对任意规模的整数边权做 MST 是可行的，参考 fib heap 伴生算法——更快的 MST。。
中位数和后缀数组。这个系列其实还有后续的几篇，丢到下面这个分类了。
其实现代计算机基本都可以直接指令了。混进来一个不是那么 O(1) 的东西，无妨。
不知道为啥没能得到推广，这不比快速幂和扩欧好写？
实际上由于很多时候要多测，用处比较有限。
The Trygub numbers。
水烂了都。
不太会 djq 分治导致的。
初见端倪。
其实比巴雷特优。
但巴雷特更加灵活。
O(1) 查询三则的后续之一。Pohlig–Hellman algorithm 的特化。
虽然标题格式很奇怪但其实是上面那篇的后续。
O(1) 查询三则的后续之一。推荐先行阅读 https://luogu.com.cn/article/5kgjhh2q。
其实可以并进上面那篇一起写，但是那个太魔怔了。
这个问题的正经做法。
本质是注意到重构树的树形结构无关紧要。
感觉其实可以推广，空间小+好写。
很神秘的东西，啃了很久才懂，但不是在这里，这篇只有一个代码。
算是比较知名的冷门算法？应用场景其实不少。
上面某篇的后续，补上了说理。
某个很好玩的东西，记之。
这个冷门算法少数有用的场合。
一点扩展。
最没啥用的一集，如果你喜欢写单调队列。
以上。