平面上圆的凸包的周长

问题如下：

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

min-max容斥

min-max容斥

$$
max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T)
$$

$$
min(S)=\sum_{T\subseteq S}(-1)^{|T|-1}max(T)
$$

虚树

之前在主站写过一篇虚树的博客，但是主站因为忘记续费然后直接没了。。。

有一个非常显然的结论，对于$dfs$序连续的三个点$x,y,z$，有$lca(x,z)\in {lca(x,y),lca(y,z)}$，这个用分类讨论什么的很容易证明

杜教筛

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

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

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

QTREE

Problem

CHANGE i ti : change the cost of the i-th edge to ti
or
QUERY a b : ask for the maximum edge cost on the path from node a to node b

Solution

树链剖分$O(nlg^2 n)$

Code

QTREE.cpp

数论中的一些常用结论

$\sigma(nm)=\sum_{i|n}\sum_{j|m}\epsilon((i,j))$

证明

常用的导数

$$(C)’=0$$

$$(x^{\mu})’=\mu x^{\mu - 1}$$

$$(\sin x)’=\cos x$$

$$(\cos x)’=-\sin x$$

$$(\tan x)’=\sec ^2 x$$

$$(a^x)’=a^x \ln a$$

$$(e^x)’=e^x$$

$$(\log_a x)’=\frac{1}{x ln a}$$

$$(\ln x)’=\frac{1}{x}$$

反演的本质

对于可逆下三角矩阵$A$（可以归纳证明$A^{-1}$也是下三角矩阵）,有$f=Ag$,那么$g=A^{-1}f$

即:

$$f_i=\sum_{j=0}^ia_{ij}g_j\Rightarrow g_i=\sum_{j=0}^ib_{ij}f_j$$

其中:
$$\sum_{k=0}^na_{ik}b_{kj}=[i==j]$$

当模数是一个64位的整数时，乘法取模过程中就会溢出。

此时有两种解决方法

一种是采取与快速幂类似的思想，时间复杂度位$O(lg)$