题目链接：HDU5828 rikka with sequece 简要题面：实现 333 中操作：区间开根，区间加，区间求和。 如果直接暴力递归，区间加操作会破坏复杂度，例如交替的 2,32, 32,3 序列，我们反复做全局 +6+6+6，再开根，单次复杂度就变成 O(n)O(n)O(n) 了。 所以我们不能完全暴力，要单独维护一下懒标记。 注意到，有很多数开根后答案相同，比如 161616 ...

替罪羊树是一个优雅的暴力，以均摊 O(log(n)) 的时间复杂度和简单的代码闻名。

treap = tree + heap，就比 BST 多了几行代码。

平衡思路超简单，最早发明的自平衡二叉树，也是查询速度最快的平衡树，

luogu 阅读链接。 定义 BST（二叉搜索树）是一种树形结构，有如下性质。 空树是二叉搜索树。 若左子树非空，那么左子树上所有点的权值均小于其根节点的值。 若左子树非空，那么其右子树上所有点的权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 操作 BST 的单次操作最坏为 O(n)O(n)O(n)，nnn 表示 BST 内的节点数，即树的形态是一条链。 节点定义 ...

前言 本文的线性基指异或线性基。 由于作者太菜了本文的语言不会特别规范。 简介 线性基简称基，它是一个数的集合，并且每个序列都拥有至少一个线性基。 线性基有三个性质： 线性基中的几个数异或后不能得到 000。 线性基中的数在异或后能得到原序列中的所有数。 线性基在保证前两个性质时，会使得基内的个数最少。 基本操作 我们用数组 ppp 表示 {ai−1}\{a_{i - 1}\}{a...

luogu 阅读链接。 前言 麻将模拟器 调了一早上结果发现 DP 中的 jjj 写成 iii 了。 题目中的和牌距离基本和向听数差不多。 文中的面子指刻子和顺子的统称。 基础操作 定义 #define endl '\n' #define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a+...

luogu 阅读链接。 灭鼠行动。 前言 其实有很多地方出题人没讲清楚，所以只保证代码可以通过本题数据。 细节 神秘射线是停止一切生理活动（包括成长），会暂停，但不会打断繁殖。 繁殖后要动一下（包括旋转），才能继续繁殖。 顺序：武器 -> 繁殖 -> 移动。 注意老鼠刚出生时的年龄。 注意时间单位和时刻的区别。 繁殖是某点恰好有两只异性老鼠。 岔路的拐弯与当前这只老鼠面对岔...

可持久化后的数据结构并不会修改什么。它把所有版本都存了下来，每次修改都会新建一个副本，然后将修改作用于副本。这样，它就拥有数据回滚、访问历史版本的能力了。

在 OI 中，红黑树可是跑的最快的，其实很好写，就 100 行够了，希望看完后你能掌握它。