平面上圆的凸包的周长

问题如下：

给定若干个圆，求包含这些圆的面积最小的凸包的周长

杜教筛

杜教筛用来解决类似求$\sum_{i=1}^nf(i)$的问题

设$S(n)=\sum_{i=1}^nf(i)$

假如我们现在找到了一个积性函数$g$，那么考虑下式（其中$*$表示狄利克雷卷积）

边分治用来解决一些点分治中一些解决不了的问题。

比如说点分治时有很多棵子树，合并这些信息时不能保证时间复杂度。

而边分治时最多只会有两棵子树，就可以很好地解决问题。

看到了[Noi2014]购票这道题目，发现了这种操作（为什么之前没想到呢。。。）

代码还没写过，先口胡一下

有根树上的DP，每个点只能从祖先转移。

定义

我们说$B(x)$是$A(x)$在模$x^n$意义下的逆元则是满足

$$A(x)\ast B(x)\equiv1(mod \; x^n)$$

分治

考虑分治

假如我们已经知道在模$x^{\lceil \frac{n}{2} \rceil}$下$A$的逆$B’$

快速傅立叶变换 FFT

对于两个多项式

$$A(x)=\sum_{i=0}^{N-1}a_ix^i$$

$$B(x)=\sum_{i=0}^{N-1}b_ix^i$$

FFT可以在$O(nlgn)$的时间内求出

$$C(x)=A(x)*B(x)=\sum_{i=0}^{2(N-1)}c_ix^i$$

其中$c_i=\sum_{j=0}^ia_jb_{i-j}$

SAM

关于后缀自动机整个算法，在这了就不多说了，感觉别人写的都很好QAQ

可以去看看参考资料里的几篇文章，感觉学过OI的应该都能看懂。。

在这里我就写一下自己的理解和一些性质和应用

简介

Min_25筛用来求一个函数的前缀和

如果函数是积性函数就可以做，如果不是积性函数的话有一部分也是可以做的

算法过程就像是在模拟埃氏筛法

时间复杂度是$O(\frac{n^{\frac{3}{4}}}{log(\sqrt{n})})$，然而我并不会证

Prufer序

一个Prufer数列和一个带编号的无根树是一一对应的

树->Prufer序

每次找这棵树中编号最小的叶子节点，将与这个点相连的点加入Prufer序，去掉这个点以及相连的边。重复这个操作直到剩下两个点。

Prufer序->树

设点集$ V={1,2,…,n} $，每次在$V$中找出最小的未在Prufer序中出现过的数，然后在$V$中删除，与Prufer序中的第一个数相连，Prufer序中的第一个数删除。重复这个操作直到$|V|=2$（Prufer序为空），最后将$V$中的两个点相连。

dsu on tree

可以用来解决一些有下列性质的问题：

1. 对子树询问
2. 没有修改

算法

算法步骤如下：

• 遍历的一个节点
  • 递归所有的轻儿子
  • 递归重儿子
  • 统计轻儿子对答案的影响
  • 计算答案
  • 如果自己是轻儿子，消除影响