当我们提到 “Treap” 的时候，我们实际上说的是 “Tree” + “Heap”。朴素的 Treap 在插入的时候给每个点一个随机的 Key，通过旋转来满足堆的性质。对于 FHQTreap，我们不再使用旋转维护，转而使用拆分和合并。

快速傅里叶变换（Fast Fourier Transform，FFT）是一种可在 $\Theta(n \log n)$ 时间内完成的离散傅里叶变换（Discrete Fourier transform，DFT）算法。
这篇文章将简单地讲解它的工作原理，以及使用 C++ 的代码实现。

这个算法的名字好毒瘤的样子。。。Dynamically Dynamical Programming，动态 – 动态规划，简称 DDP。 我们先考虑简单的动态规划。有一个经典问题叫做树上最大权独立集。比如 没有上司的舞会。 那么我们可以设 $f_{u,1}$ 为 $u$ 在独立集内的最大收益，$f_{u,0}$ 为 $u$ 不在独立集内的最大收益。转移方程如下： $$f_{u,1}=\sum_{v\in son}f_{v,0}$$ $$f_{u,1}=\sum_{v\in son}\max (f_{v,0},f_{v,1})$$ 现在我们要支持的操作是动态修改某个点的权值，比如 洛谷模板。 为了快速维护，我们先对整棵树做一个树剖，然后对每一条重链分别进行 dp。 对于重链上的每个点，先根据轻儿子的 $f$ 维护 $g_{u,1/0}$： $$g_{u,0}=\sum_{v\in lightson}\max(f_{v,0},f_{v,1})$$ $$g_{u,1}=\sum_{v\in lightson} f_{v,0}$$ 对于重链上的点，则有： $$f_{u,0}=g_{u,0}+\max(f_{heavyson,0},f_{heavyson,1})$$ $$f_{u,1}=g_{u,1}+f_{heavyson,0}$$ 这样，树上的问题就转化成了序列上的问题。我们可以对于每条重链维护一颗线段树。修改一个点的值就在这个点所在重链的线段树上修改，最后改变了重链顶端的点的 $f$ 值，进而影响了其父亲的 $g$ 值，反复向上修改，时间复杂度就是 $\Theta(log^2n)$ 的。 问题来了，如何用线段树维护 $f$ 呢。我们重新定义矩阵乘法。对于 $C=A\times B$，有 $$C_{i,j}=\max\limits_{k=1}^{n}(A_{i,k}+B_{k,j})$$ 于是，重链上的转移可以写成这样的矩乘 $${\left[ \begin{array}{cc}g_{i,0} &g_{i,0}\\ g_{i,1} […]

NOIP 2018 游记。