【Note】Splay / 文艺平衡树

定义 Splay 是一种可以自我调节的二叉搜索树。它在 $\Theta(\log n)$ ​ 的均摊时间内执行基本操作,例如插入,查找和删除。对于许多非随机操作序列,Splay 比其他搜索树表现更好。 核心操作 我们提到 Splay 可以 “自我调节”,这一性质使得它能维持树形结构,保证复杂度。自我调节分为两部分:旋转 (rotate),以及伸展 (splay)。 旋转 伸展 实际运用 作为二叉搜索树,它能完成所有二叉搜索树都能完成的基本操作。当然,它也可以作为区间树完成诸如区间翻转的操作,正是这一性质使得它可以作为 Link Cut Tree 的辅助树。 代码 普通平衡树 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入 $x$ 数删除 $x$ 数(若有多个相同的数,因只删除一个)…

【笔记】Dirichlet 相关

Dirichlet Convolution Definition $$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{xy=n}f(x)g(y)$$ Example $\sigma_0=1*1$$\sigma_1=I*1$$I=\varphi*1$$\epsilon(n)=\mu*1$ Property 交换律:$f*g=g*f$结合律:$(f*g)h=f(g*…

【笔记】简单数论函数集合

Intro 咕了一年的集合。NOIp 内容。 (实际上只讲了两个函数) 常见数论函数 $\epsilon(n)=[n=1]$$1(n)=1$$id_k(n)=n^k$$I(n)=id_1(n)=n$$\sigma_k(n)=\sum\limits_{d|n}d^k$$\varphi(n)$$\mu(n)$ 欧拉函数 $\varphi(n)$ Definition $\varphi(n)$ 等于小于等于 $n$ 且与 $n$ 互质的正整数个数,即 $$\varphi(…

【歌单】Frustrated

还有什么能够盛开 你知道我一直很乖 我们的过去是一片稻田 还有什么值得期待 mama don’t let me down mama go with the wind 蒲公英和炊烟都在等你 你的孩子一直很乖 mama don’t let me down mama go with the wind 蒲公英和炊烟都在等你 你的孩子一直很乖…

【UOJ Round #6】懒癌 / 题解

题目描述 当地共有 $2^n−1$ 个村庄,每个村庄住着 $n$ 户人家,门牌号分别为 $1,2,…,n$,每户人家家里养着一条狗。恰逢无药可治的懒癌流行,人人自危。每个村庄都有至少一只狗得了懒癌。一个村庄中,门牌号为 $i$ 的人家的狗要么得懒癌,要么不得懒癌,一共 $2^n$ 种情况,再去掉都没得懒癌的情况,一共 $2^n−1$ 种。这每种情况都会发生在恰好一个村庄中。 这天来了个善良的人来到每个村庄中,告诉所有人一个爆炸性的新闻:“你们村里至少有一只狗得了懒癌!” 每个村庄中每户人家都不知道自己的狗到底是懒癌还是可爱,但是他能一眼看出某些人家的狗有没有得懒癌。由于这个社会里人与人之间的信任已经崩塌,一个人即使看出别人的狗是否得懒癌也不愿告诉他。 可以用一个 $n$ 个结点的有向图来描述可见性,$v$ 到 $u$ 有一条有向边表示门牌号为 $v$ 的人家能看出门牌号为 $u$…

【HNOI 2016】序列 / 题解

题目描述 给定一个长度为 $n$ 的序列 $a$,每次询问 $[l,r]$ 内所有连续子区间的区间最小值。 思路 我们分别讲解如何使用离线 / 在线算法解决本题。 离线 / 莫队 使用莫队将问题离线后,我们需要思考如何从 $[l,r-1]$ 的答案推至 $[l,r]$ 的答案。 首先,我们知道一共新增了 $r-l+1$ 个,以 $r$ 为右端点的区间。如果将 $[l,r]$ 中区间最小值的位置记为 $p$,这些区间可以根据是否包含 $p$ 划分为两部分:对于包含 $p$ 的那 $p-l+1$ 个区间,显然它们对答案的贡献都等于 $a[p]$。 对于剩下的 $r-p$ 的区间,…

【笔记】Borůvka's Algorithm

Borůvka 算法是一种计算图最小生成树的贪心算法,于 1926 年被 Otakar Borůvka 首次发表。 基本原理 首先,我们会找到图上每个节点到其他节点的最短边,然后把这些边加入森林中。我们不断重复这个过程,即每次给森林中每棵树找到连接其他树的最短边,然后将这样的边加入森林。 每次操作会减少森林中树的数量至少一半,于是我们可以在对数次操作内完成这个算法。 均摊复杂度为 $\Theta((n+m)\log n)$。 典型例题 对于大多数的图,Kruskal 和 Prim 已经非常优秀了。这里我们给出一个特殊情况,在这种情况下 Borůvka 的效率比前两者高得多。 给定 $n$ 个二维平面内的点,两点之间边权为两点的曼哈顿距离,求这些点的最大生成树大小。 在这里,图中边的数量达到了 $n^2$ 级别,不适宜直接计算。 因为边权是曼哈顿距离,我们发现我们可以较快地算出对于每棵树,到它距离最远的点的距离,Borůvka 算法可以在 $\Theta(…