笛卡尔树
一棵二叉树，结构上满足左子树的下标小于自己和右子树，右子树的下标大于自己和左子树。且键值满足堆的限制。
栈构建。维护当前根节点向右一直跳的右链，那么按数组下标顺序插入，每次插入，从栈顶一个个考虑，如果当前的节点的键值不配当他的父亲，那么就弹栈并继续，如果栈空或者找到一个可以当他的父亲的节点，将这个节点的右子树设成当前点的左子树，并将当前点的父亲设为这个节点。
KMP
\(f_i\) 表示最大的 \(S_{1,f_i}=S_{i-f_i+1,i}\)。匹配别人和自己都是类似的跳 f。
manacher
首先构建上在第一个位置插入奇怪字符，其余相邻字母间和第一个字母前、最后一个字母后插入一个相同的另外特殊字符
设 \(f_i\) 表示以 \(i\) 为回文中心的最长回文串，维护 \(mid,r\) 表示当前回文串最靠右的能达到 \(r\)，其回文中心是 \(mid\)，那么每次考虑新位置只需设初值为 \(\min(f_{mid + mid-i},r-i+1)\)，然后暴力扩展即可。
欧拉路径/回路
经过所有边恰好一次的路径/回路。
有向图存在欧拉回路的充要条件的图联通，且所有点满足入度等于出度。路径就是一个点入度比出度大一，就是终点，另一个点出度比入度大一，就是起点。
无向图存在欧拉回路就是所有点度数为偶数，路径就是有且只有两个点度数为奇数，就是起点和终点。
遇到一些有关度数的题可以往这方面考虑。
求法的话，直接从起点开始搜索，并将搜到的边删掉（无向图则双向都删）即可。过程中，要求经过点顺序的话是搜完有关这个点的边再丢栈里，边就是搜完边再丢栈里，答案就是栈顶到栈底。
子集卷积
求 \(c_i=\sum_{j|k=i,j\&k=0} a_j b_k\)。设 \(ppc(i)\) 是 \(i\) 二进制下的 \(popcount\)。
考虑转成或卷积，就是 \(c_i=\sum_{j|k=i,ppc(j)+ppc(k)=ppc(i)}a_jb_k\)。
那么扩展到二维，设 \(X_{i,j}\) 表示 \(ppc(*)=j\) 的序列，则变成了：
\[c_{i,b}=\sum_{c+d=b}\sum_{j|k=i}a_{j,c}b_{k,d} \]那么后面那个就是或卷积，用 FWT 解决，前面那个枚举一下 \(c,d\) 即可。
复杂度 \(O(n^2 2^n)\)。
标签：ppc,复习,乱七八糟,mid,节点,算法,回路,sum,回文 From： https://www.cnblogs.com/infinities/p/17248658.html