冰龙草的算法随笔
1、桶
桶其实就是一个容器，种类不限。大多数时候，“开桶”指的是在每个位置或每个节点下建立一个容器，由于容器的内存为动态，在对时空复杂度分摊的正确评估下，可以存放临时数据。例如“天天爱跑步”中在每个节点建立两个vector来储存差分值。（准确地说，节点通过一个索引，通常是自己的编号，来指向一个预先开好的容器数组）
树上桶合并：假设桶的类型为vector，初始存放每个节点的点权，现在希望将桶从叶子全部合并至根节点。假设节点v1,v2…vk是u的子节点，那么把桶合并到u上时，只需要将u与vi一个个合并即可，具体操作为：遍历较小的桶，将所有元素压到较大的桶，然后让u的索引指向较大的桶。这样的合并过程，总复杂度为$O(nlogn)$，证明如下：对较小桶而言，合并后的新桶大小至少为自己的两倍，换而言之，对一个元素执行取出和压入操作，新桶大小必然大于等于旧桶的两倍，这意味着一个元素最多被执行logn次该操作。
分块其实就是开$sqrt(n)$个大小为$sqrt(n)$的桶，单独维护桶内信息，支持对桶内信息的暴力修改（每次操作最多只暴力修改两个桶）。这启示我们可以某一类信息单独维护。
例题：查询以某一节点为根的子树内，不同点权的数量。我们以set为桶进行合并即可。这题也可以用dfs序上的莫队轻易解决。
对桶来说，其空间复杂度需要经过正确的评估，以下以几类桶为例：
（1）所有位置开桶，桶中储存差分信息（通常是不同种类元素的差分），用于在顺序遍历时累和前缀。由于一次操作产生的差分有限，所有桶的空间复杂度为O(n)。
（2）单点修改并查询一段连续区间有几个元素z（0<=z<n）。我们开set桶*n个，st[z]表示z的的桶，其内储存z出现过的所有下标，问题转化为在该桶内查找下标区间。显然，所有桶的大小不超过n。
（3）按位进行区间修改，并查询一段连续区间中，所有数值在二进制下第k位/前k位的1的总数。我们可以建立线段树，在每个节点上开大小为32的数组，记录每一位的总和。如果修改操作只修改位，合并时就只更新受改动的位。
（4）与（3）类似，对于字母串，每个节点开大小为26的数组，来单独记录每种字母的信息。
2、启发式合并
这道题给了我很多的思考，启发式搜索的原理就不赘述了，以下是对这道题的解答
定义一个桶序列$v[]$，用于存放下标，接着定义一个数组pt记录颜色，$pt[x]=y$表示颜色x的所有下标存放在桶v[y]中（或者说，颜色x指向桶y）。我们还有一个数组ar用来表示题目所述的序列，**$ar[i]=y$表示$i$这个下标当前存放在编号为$y$的桶中**（这就是困扰我一下午的地方，ar存放的不是颜色！）。请注意，在此之后，所有的颜色转换操作，诸如将颜色a染为b，就是把$v[pt[a]]$中的元素转移到$v[pt[b]]$中，然后置空$v[pt[a]]$，这样就不用暴力扫描颜色下标了。
一开始，我们不妨令所有$pt[x]=x$，这样就可以直接把题目给的初始颜色序列写到ar中。在之后的操作中，比如将颜色a染为b，会有如下两种情况（设pa, pb为pt[a],pt[b]的引用）：
（1）$sz[a]<=sz[b]$。这很简单，我们把v[a]的元素逐一加到v[b]，然后清空v[a]就行了。
（2）$sz[a]>sz[b]$。我们把v[b]的元素逐一加到v[a]，然后清空v[b]，紧接着交换a,b（a,b是引用，其实就是交换指针），pa便还是指向了空桶。其实我们可以一开始便交换a,b，然后执行（1）就行了。
然后对每个被移动到新桶的下标，把它在ar中对应位置的值也修改为新桶编号。这样，如果ar[i]==pt[x]，就可以说明i位置的颜色是x（当然，只能用作判断，我们无法通过ar[i]得知其对应的具体颜色）。
以上就是题解了。我们还能在指针上换个思路——考虑到vector的swap是O(1)的，因此我们甚至可以舍去pt数组，直接使用桶序列。
3、rope
rope可以o(1)继承上一个版本。（内部维护了平衡树的指针），写法如下：s[i]=new auto(*s[i-1])
rope可模拟可持久化的数组、双向队列，可以logn地删除、修改元素（插入元素最坏是O(n)，压入元素logN）。然而其空间开销极大，不宜在超过1e5的数据下使用。c++ STL rope小结 - 代码先锋网 (codeleading.com)
4、CDQ分治
最详细的CDQ分治讲解【CQOI2011动态逆序对】 - shadowice1984 的博客 - 洛谷博客 (luogu.com.cn)
树套树是模拟整个过程,而CDQ是判断整个过程。树套树空间大,CDQ空间小。树套树强制在线,CDQ离线。树套树有一定的范围,而CDQ的范围是单个变量的最大值 (如 int64)
5、滞后操作
典型的例子是云刷题第8题，其中的思想是，如果我们已经将值为x的元素累加进结果，后续想要将此值修改为y，则可以向此集合+y-x。更一般地，假设此元素的上一个值为lst，则 “从集合中找取出元素（有的话）->改值为now->放回”的过程，可简化为向结果加上now-lst（lst的初值为0，表示未加入集合）。
在黑白树 (nowcoder.com)中，我们用dp[x]表示在x的子树中已选择的点中的最大贡献，用tx[x]表示未选择的点中的最大贡献。对当前节点u，首先把u计入tx[u]中，表示预选，然后用子节点的dp[v]更新dp[u]。如果dp[u]满足不了不用选u，说明需要选择u，此时可以直接令dp[u]为tx[u]。我们不在乎tx[u]所指的具体是哪个节点，只想要用到这个最大贡献。
至于提供了最大贡献后的tx[u]则不用管，可以继续传递给父节点。关于tx[u]，本题有个重要性质：只有最大值有机会起作用，次大值永远不会被选中（一旦最大值被选，就没有选次大值的机会）。
6、猜想性质
我一直坚信面对问题时要大胆猜测。
我们知道，当一个猜想同时满足必要性和充分性时，也就是——
必要性：满足这个猜想的策略都能得到正确结果
充分性：得到正确结果的策略都满足这个猜想，或者不满足这个猜想的策略都得不到最优解。
此时这个猜想就摇身一变，成为了我们挖掘出来的性质。
但是大多数时候并没有太多精力去验证猜想，所以我大致作一个分级：
- 强猜想：满足必要性或充分性之一，值得大胆实践
- 中猜想：满足弱必要性和弱充分性。弱必要性：找不到满足这个猜想的不正确结果（用规律来推测样例）。弱充分性：找不到不满足这个猜想的正确结果（从样例找规律）。
- 弱猜想：满足弱必要性或弱充分性之一，题目一般很难自己造数据。
7、线段树合并
在经历一些题目后，我扫除对权值线段树的一些错误点
首先，当线段树b被合并到a后，b将处于一个不可查询不可修改也不可再被合并的移后状态。这是因为，b的一部分节点被共享给a，而a在后续的合并中，又免不得会对这部分节点做更新，因此线段树合并几乎只在树上问题才能发挥作用。
特殊情况：
1 合并空树
2 重复合并，自我合并 （这两种情况十分危险，宜注意排除）
8、树形背包
9、
【每日一题】2021年3月29日题目 划分树_牛客博客 (nowcoder.net)
10、二进制构造
（1）给予一组元素，每个数互异且遍布了2的幂，即 $2^0,2^1,2^2,2^3,2^4…$。定义一个集合的大小为这个集合中的元素之和，我们想知道在上述序列中，第k小的子集的大小。很显然，这个第k小子集的大小就是 k 本身。比如k是(1001)，结果便是（$2^0+2^3$）。
如果我们去掉某些权位，比如得到 $2^0,_\ ,2^2,2^3,_\ ,2^5,…$，再询问第k小。那么，对于序列的所有子集的值，在二进制表示下，位权缺失的位都为0，无视这些位后仍可视作二进制数。于是我们可以直接剔除缺失部分，以其他数代位。对于k是(1001)，结果便为（$2^0+2^5$）。
（2）
Ehab the Xorcist (异或性质，构造)-CSDN
11、线性基
在将序列的每个元素插入线性基时，如果当前元素可以由前面的元素异或得到，那么此元素就不会插入成功（0一定不能插入），这就保证了线性基没有异或和为0的子集。在表示线性基的数组中，最后的非0数就是最小的线性基，同时也是原序列所能异或出来的最小数字（如果出现不能插入的元素，则最小异或和为0）。
线性基中，对于一个向量x，选择大于x的若干线性基元素相互异或，结果必然大于x（因为最大的那个数，其最高位一定做贡献）；选择小于x的若干线性基元素相互异或，结果必然小于x。假设前者结果为a，后者结果为b，a^b也一定大于x。
一个线性基异或上另一个不同的线性基，并作为自己的新值，这并不改变整个线性基的性质（线性基只有元素数量是固定的）。
第k小
从大到小枚举每一个线性基d[i]，从它的第二高位往低位扫，如果扫到d[i]在第j位是1，那么就异或上d[j]（d[j]最高位是1），这样就消去d[i]在第j位上的1。当然d[ j ]这个向量可能不存在。那么原本该位的1不变。那么处理完一个线性基之后，应该大致是长这个样子的（x表示0或1）：
1xxxx0xxx0x
1xxx0x
1x
也就是，每个线性基元素的最高位1，只会由自己贡献，这依旧满足线性基基本性质。我们把这些新元素放入新数组_base，无视旧数组中的空向量，记新数组大小为cnt。_base数组具有与二进制基数一样特点：
- 每个向量选或不选；
- 往一个集合中加入新向量，或者把集合中一个元素换做更大的向量，集合异或和会变大；
- 比向量X小的所有向量的异或和，仍小于X。
如果k的第 i 位为1，那么结果就异或上 _base[i]，最后便得到了第 k 小。
在_base数组中（从小到大，从0下标开始），小于等于第 i 个元素的子集数量共 1<<i 个（之前元素任意组合数量+只取自己。如果在取了自己后再取任何数，都会比自己大）。
12、斜率优化dp
整理不等式，得到斜率表达式。每到一个 i 时，可以立即获取当前的切线斜率k（假定k恒负）。对于由两个候选点连成的直线而且，设斜率为w，若w>k，则后者更优，否则前者更优。从暴力的角度讲，我们可以这样去找到目标转移点：两两枚举点，把被淘汰的一方标记，最后没被标记的点就是解。
然而对每个 i 都这样做显然复杂度不理想，于是我们先作分析，得出结论(过程自行了解)：最优点一定落在最外围的凸包上。这里k为恒负，所有应该是上凸。如果一个点不在凸包上，那么无论k为何值，都一定会被淘汰。对这个凸包，我们考虑横坐标相邻的点就行了，对于不相邻的点之间连的直线，在这两点间的相邻点连线中肯定有的斜率比它高和比它低（拉格朗日中值定理）。
上凸或下凸，跟题目要最大还是最小有关，与k的正负无直接关系。找到最优点 j 后，按朴素dp式从dp[j]转移到dp[i]即可
除了根据优劣关系筛最优点外，另一种等价思想是：将原式整理作b=max/min(y+kx)，b中包含了dp[i]和其他定值，y中包含了只与j有关的值，k与i有关，x与j有关。于是问题变为找到一点(x,y)，在给定的k下，截距最大/最小，那么显然直线应该切在凸包上。最后由b得到dp[i]。个人更喜欢这个思考方向。
如果 i 与横坐标没有单调关系呢？动态规划问题一般与连续的 i 有强联系，因此只能老老实实按横坐标插入相应位置，然后采用平衡树维护。
斜率优化也有很多思想值得借鉴，比方说，虽然不能直接找到最优点的特征，但是可以通过点与点之间的优劣关系，来定位最优点的位置（先假定不等式，再解出特征关系）。
单调栈求凸包也是一个巧妙的思想，仔细想想，毕竟凸包的整体结构是确定的，并且任一区间的局部轮廓也一定是该区间的点的凸包（子结构最优），因此有着转移策略。
13、dfs树补充
对两个边集，我们定义异或操作：去除重复边，合并其余边。
两个要补充的性质：
- 对于图上的环，把仅有一条返祖边的环称作基环(我自己称呼的)，则任何环都可以由基环异或得到。
- 对一条从指定起点到终点的通路，相同边可走多次，且走过偶数次的边无贡献，则将这条通路与一个环（在同一个连通分量中）异或后，得到的新路仍然是合法的通路。
结论：可以通过基环来“修正”dfs树上的路径。这道最大XOR和路径是最典型的应用。
希望这两点能在以后，对图与dfs树的性质的挖掘有所启发。
14、树模型补充
在图中，树是这样这样一种结构：每个点都可以找到唯一一个与之配对的点，唯独一个点没有配对（如果所有点都有有配对，则考虑基环树）。每个节点与其父节点形成配对，如果我们不断的移除掉叶子，最后就会剩下唯一的无配对点。
如果点与点的配对有代价，就可以运用到最小生成树。
15、暴力
遇到一个问题，当很难找到什么可以证明是正确的解法，而AC的人又很多时，这道题大概率是暴力题或者打表题。
分段暴力
有这样一类题目，其数据范围虽然很大，但是我们可以分成几个部分，其中小范围使用暴力求解，而大范围根据普遍规律求出（适于随着数据越大越呈现出简单规律的题目，比如进制相关的问题），或者我们有办法使其归约到小范围中（比如我们可以确定答案的情况有限）。
比如K-wyh的数列，在模一个数的意义下，有通项公式的数列必然存在循环节，如这里的$f[i]=(f[i-1]+f[i-2])%c$，显然在前c*c项中至少存在一个循环节。
另外，$10^{12}$到$10^{14}$通常意味着存在$O(\sqrt n)$的做法，