其实差不多是把所有谷上的模板题代码搬来了QwQ 树论 LCA P3379【模板】最近公共祖先（LCA） include<bits/stdc.h> usingnamespacestd; constintmaxn=51e6+5; intf[maxn][25],dep[maxn],head[maxn],nxt[maxn],to[maxn],cnt,N; voidadd(intx,inty) { to[cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; } intlca(intx,inty) { if(dep[x]<dep[y])swap(x,...

珂朵莉树，又名老司机树（OldDriverTree，ODT），是一种暴力数据结构，是由数据结构毒瘤、Ynoi出题人lxl发明的一种对随机数据十分有效的暴力数据结构。这里使用set实现的珂朵莉树时间复杂度为$O(n\logn\logn)$。 珂朵莉树主要应用于区间的“推平”操作，就是对一个区间内的所有值进行修改。当然不局限于单一的推平，可能还有其他操作，这时我们就需要用到珂朵莉树。 考虑一下，我们把几个区间推平之后，整个序列就会变成好几段有相同数的区间： $5$ $5$ $42$ $42$ $42$ $42$ $2$ $3$ $3$ $3$ 我们用一个结构体来表示每个数字相同的段：...

Manacher算法，俗称马拉车算法，是一种解决最长回文子串问题的算法。 咕咕咕 updon2023/2/19： 不咕了，开始写！ 为什么突然想起来更新了捏？主要是因为在Ybt的哈希章节中出现了这个： 这不就是马拉车吗？数据范围是最多$10^6$，数据相对于谷的马拉车模板弱了点儿。 所以，马拉车，开搞！ 对于一个普通的字符串，我们要想求出它的回文子串需要考虑它的长度是奇数还是偶数。奇回文串的对称中心是一个，偶回文串的对称中心由两个字符共同组成。 而我们的Manacher算法的第一步，就是想办法让字符串的每一个回文子串都是奇回文串。我们把一个字符串的每两个字符之间插入一个相同字符（用啥都...