ACM

可持久化数据结构是指在每次修改后都保存了修改前版本的数据结构。在可持久化数据结构中，我们可以很方便的追溯到某次修改前的版本，以此来完成某些操作。简单来说，对于nnn次插入操作，我们就存储nnn个版本，第iii个版本对应了前iii次操作后的数据结构。当然，不可能真的存nnn个完全独立的版本，空间会直接爆炸(～￣▽￣)～。可以注意到，对于Trie和线段树等数据结构来说，每次插入只改变了一条链上的节点，因此对于每次插入操作，我们只需要新建这条链上的节点，而其他的节点可以直接白嫖上一个版本的。 常用的可持久化数据结构主要有可持久化的Trie和可持久化线段树。 可持久化Trie 首先，既然有nnn个版本，当然就对应了nnn个根节点，从不同的根节点开始遍历就可以得到不同版本的数据结构。下面简单演示一下可持久化Trie的插入过程。 最开始是一个空的Trie，插入一个字符串no（黑色节点表示根节点） 然后插入一个字符串game，由于这整个字符串都属于要改变的节点，所以都要新建，同时，为了从新建的根节点能够访问到以前插入的字符串，新的根节点也要有边连向n 继续再插入一个字符串no，但是no之前已经插 ...

（本文章主要涉及Nim博弈及相关变种，二分图博弈以后再补_(:з)∠)_） Nim博弈是最经典的博弈论问题之一，一般可以描述为如下：两个人轮流从若干堆石子中取石子，每次只能取一堆石子中的任意个，最后无法取（即所有石子都被取完）的玩家判负。Nim游戏拥有简洁的规则和优雅的结论，也是SG函数的基础。 基本概念 首先明确一些概念，Nim博弈是公平组合游戏（Impartial Combinatorial Games, ICG）的一种，所谓公平组合游戏，需要满足以下几个条件 有两个玩家 两个玩家轮流操作，在一个有限集合内任选一个进行操作，改变游戏当前局面 一个局面的合法操作只与游戏当前局面有关，与当前玩家和次序等其他因素无关（公平） 无法操作者判负 为什么要提这个呢？因为从这些条件里，我们可以得出一个最基本的定理：一局游戏的胜负只与当前的局面有关，与当前是哪个玩家在操作无关，因为当局面确定，由于合法操作不受其他因素影响，那么其所有可以进行的操作与操作后的局面都是确定的，在两个玩家都绝对理性的情况下（这是大前提，否则就没有意义了），其胜负自然也是确定的。 那么，我们就可以把所有局面分成两种：必 ...

BSGS算法（baby step giant step，大步小步算法），又叫北上广深算法（不是），是一种基于中间相遇思想求解离散对数的算法，即求解类似于ax≡b(modm)a^x\equiv b\pmod max≡b(modm)的方程。 BSGS算法 首先介绍最普通的BSGS算法。普通的BSGS算法要求mmm和aaa要互质，既然互质，那么根据欧拉定理 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1\pmod m aφ(m)≡1(modm) 也就是说，ax(modm)a^x \pmod max(modm)以φ(m)\varphi(m)φ(m)为周期循环，那么如果方程有解，解一定在000到φ(m)\varphi(m)φ(m)之间，如果暴力枚举，当mmm为质数时φ(m)\varphi(m)φ(m)最大为m−1m-1m−1，最坏复杂度为O(m)O(m)O(m)。 普通的BSGS算法就是对上述暴力算法的一个优化，我们可以把xxx改成At−BAt - BAt−B，那么原式变成aAt−B≡b(modm)a^{At - B} \equiv b \pmod maAt−B≡b(m ...

Splay树，即二叉伸展树，是一种非严格平衡的二叉搜索树，由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明（摘自百度百科）。相比与AVL、红黑树而言，Splay树不需要额外地存储平衡信息，因此显得更为简洁，代码实现也较为简单（指150行代码），同时具有很强的扩展性，常用于算法竞赛中。 至于我为什么突然想要学Splay树，因为这是Tarjan发明的……没错，就是求强连通分量、割点、桥的Tarjan算法的那个Tarjan。事情的起因是我最近刚学完强连通分量，然后查了一下Tarjan的资料，发现原来是祖师爷级别的大佬，拿过图灵奖，发明了很多图论的重要算法和数据结构。于是就对Splay树产生了兴趣，虽然这玩意已经明显超过了我的算法水平（刚学完强连通的蒟蒻），但我还是自不量力毅然决然地花了两天手搓了Splay，然后又花了一天的时间调试。 那么废话了那么多，接下来正式介绍Splay树 （以下内容和代码部分抄袭参考自oiwiki和其他人的博客、文章等） （图片均使用开源网站ioDraw绘制，感谢开源者的贡献） 基本成员 S ...

最近花了两天时间学了下树状数组，然后感觉堪比玄学，故写篇文章总结一下。 2024.08.07 UPD：添加了树状数组的树形结构解释，与树状数组上二分。 树状数组（binary indexed tree），也叫BIT，又以其发明人名字被称为Fenwick树。树状数组利用二进制下标来维护区间和，能够做到以log⁡n\log{n}logn的复杂度进行单点修改和区间求和，同时配合差分数组等结构，还能做到区间修改、单点查询和区间修改、区间查询等功能，相比与线段树来说更为简单和优雅。 基本知识 树状数组最为重要的一个设定就是lowbitlowbitlowbit——二进制最低位的1及其后面的0所组成的数字，相比与前缀和，树状数组的每一位维护的是(i−lowbit(i),i]\left(i-lowbit(i),i\right](i−lowbit(i),i]的区间和，比如6，二进制为110，那么这一位维护的就是原数组6到4100的区间和（不包含4）。 那么要如何计算一个数的lowbitlowbitlowbit呢？如果用一个1作为check来判断每一位是否是1，那么代码大概长这样： 1234for(in ...