RenaMoe's Blog

题面

两个数列 \(a,b\)，求最少相邻两数交换多少次使得 \(\sum_{i=1}^n{(a_i-b_i)^2}\) 最小

题面

在坐标系第一象限有一些点，用一些经过原点、开口向下的抛物线 \(y=ax^2+bx\) 覆盖所有点，最少需要多少条

先贴个板子，总结有时间在再说

\(\rm SAM:\ Suffix\ Automaton\) ，后缀自动机。

远古博客，有许多纰漏，慎重食用！

难理解，但代码好写（当初敲完模板题没总结，现在忘光了QAQ）

总体上是 后缀 trie + parent tree ，构成一个可以表示所有子串的 DAG

求解关于 x 的 \(a^x\equiv b\pmod p\) 同余方程的算法。

快速沃尔什变换，用于处理 \(C_k=\sum_{i\otimes j=k}A_i*B_j\) （\(\otimes\) 是集合运算符）几何卷积运算

对于 \(A\) 求出 \(fwt[A]\) ，使得 \(fwt[C]=fwt[A]*fwt[B]\) ，于是就 \(O(n)\) 了

用于处理高维空间组织点

大概就是在某个维度下从坐标中位数二分，最后形成一棵二叉树

题面

求长度 \(n\) 的交错序列的方案数。

左偏树本质是堆，在满足父亲比两个儿子的\(val\)都大（小）的时候保证

\[dist[ls] >= dist[rs]\]

\[dist[x] = dist[rs] + 1\]

将线段树或者权值线段树可持久化。