Codeforces 311B
题意：有$m$只猫，放在一些位置$[1,n]$，每个位置之间的距离$d_i$，每个猫出现的时间$t_i$，假设派出$P$个人，可以自由安排其出发时间，沿途将已经出现的猫取掉，猫等待的时间是被取的时间减去出现的时间。现在有$P$个人，问总时间$T$最小是多少。

考虑设$a_i= t_i - \sum_\limits{j=1}^{h_i} d_i$，那么这个时间即为人什么时候出发，能取到猫$i$。
那么如果人出发时间为$g$，则该猫的等待时间为$a_i - g$(能取到的话)。
那么这样题目清楚了很多，如果$P=1$，那么答案就是最大值减去其他所有值的和。

考虑$p \leq 2$的情况：
我们可以发现这些猫现在的$a_i$和位置没有关系了，可以考虑将$a_i$按从小到大排序，然后发现只用用$P$个序列覆盖$a_i$即可。
这样还是麻烦，注意观察，序列一定是子串。因为不连续的一定不优，假设有$[1,3],[4,5],[6,8]$，则如果$[1,3], [6,8]$一个人，那么一定没有$[4, 5], [6,8]$一个人优。

所以可以开始DP：设$dp(i,j)$为分了$i$段，前$j$只猫的最小等待值，则
$$
dp(i,j)=\min_{1 \leq k \leq j} (dp(i-1,k)+a_j \cdot (j-k) - (\operatorname{sum}(j) - \operatorname{sum}(k)))
$$
直接枚举会炸。发现这里有$j,k$的乘积项，考虑斜率优化。
转化，得
$$
dp(i-1,k)+\operatorname{sum}(k)=dp(i,j)-a_j \cdot j + a_j \cdot k +\operatorname{sum}(j)
$$
那么决策可以写作点$(k, dp(i-1,k)+\operatorname{sum}(k))$
用这个算下斜率，即可斜率优化，注意开数组简化$dp(i-1,k)+\operatorname{sum}(k)$
并且一定要斜率大减小，避免负数对叉积的影响

知识点
1、斜率大减小，避免负数对叉积的影响
2、适当开数组简化一些东西

BZOJ 3529
题意：给定多组$n,m,a$，设$d_1(n)$为$n$约数和，求
$$
\sum_{i=1}^n \sum_{j=1}^m d_1(\gcd(i, j))
$$
并且满足$d_1(\gcd(i, j)) \leq a$

不考虑$a$的限制，枚举约数
$$
\sum_{d=1}^n \sum_{i=1}^n \sum_{j=1}^m d_1(d)[gcd(i,j)=d]
$$
发现$d_1(d)$与$i,j$无关，移到前面
$$
\sum_{d=1}^n d_1(d) \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=d]
$$
将后面用反演套路化简，得
$$
\sum_{d=1}^n d_1(d) \sum_{k=1}^{\lfloor \frac nd \rfloor} \mu(k) \lfloor \frac n{kd} \rfloor \lfloor \frac m{kd} \rfloor
$$
设$T=kd$，则
$$
\sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|T}d_1(d) \mu(\frac Td)
$$
如果没有$a$的限制，则线性筛后面的函数即可。
考虑$a$的限制。
只有$d_1(x) \leq a$的才会有贡献。
所以将$d_1(x)$从小到大排序，将询问离线后按$a$从小到大排序
每次按照$a$的单增补齐到$a$，补齐即枚举$x$的倍数进行增加。
维护一个单调修改区间查值的数据结构，用树状数组维护之。
时间复杂度：$O(n\log ^2 n + q \sqrt n \log n)$

poj 2374
题意：给你$n$个围栏，对于每个围栏你必须走到其边上才可以往下跳，现在问你从初始最高位置的$n$个围栏，到原点，水平走过的路程最少是多少？

设$dp(i,0/1)$为前$i$个围栏在左/右的最短距离，则
$$
dp(i, 0)=\min(dp(a, 0) + |x_i - x_a|, dp(a, 1) + |x_i - y_a|) \\
dp(i, 1)=\min(dp(b, 0) + |y_i - x_b|, dp(b, 1) + |y_i - y_b|)
$$

其中$a,b$是这个围栏端点掉下去能掉到的围栏，这个可以用线段树染色维护。
知识点
1、线段树优化 DP 不一定是要维护最优值

BZOJ 2005
题意：
给定$n,m$，求
$$
2 \times \sum_{i=1}^n\sum_{j=1}^m (\gcd(i,j) -1)
$$

按照套路反演以后得到

$$
\sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac nd \rfloor} \mu(i) \lfloor \frac n{di} \rfloor \lfloor \frac m{di}\rfloor
$$

然后我们设$T=di​$，则

$$
\sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|T} \mu(d) \lfloor \frac Tk \rfloor
$$

设$h(T)=\sum_{d|T} \mu(d) \lfloor \frac Tk \rfloor$，则可以线性筛。

也可以发现这就是欧拉函数，直接筛欧拉函数即可。

答案为
$$
2 \times \sum_{i=1}^n\sum_{j=1}^m \gcd(i,j) - nm
$$

BZOJ 1787
BZOJ 1832
题意：给一棵无权无根树，每次询问三元组$(x,y,z)$，求树上到$x,y,z$的距离最短的那个点，输出距离。
很容易想到就是三对$LCA$取最小值。
这里主要是想要讲的是树上三个点的三对$LCA$必有两个相同
然后其实这题答案就是那个不一样的那个$LCA$。

BZOJ 1233
题意：给出$n$个数，将这$n$个数按顺序分组，并且每一组都不能比前面一组和大。求最大能分几组。
引理：

在多种可行的堆叠方案中，至少有一种能使层数最高的方案同时使得底边最短。
即底边最短的，层数一定最高。

证明略去。可以感性认为底边越短，层数就能堆得越高。

所以可以设$dp(i)$为$[i,n]$的最小底边长度，$g(i)$为其层数，$\operatorname{sum}$为$n$个数前缀和。
则
$$
dp(i)=\min_{i < j \leq n, dp(j)\leq \operatorname{sum}(j - 1) - \operatorname{sum}(i - 1)}(\operatorname{sum}(j - 1) - \operatorname{sum}(i - 1))
$$

最小的$j$更优，因为$\operatorname{sum}$的单调性。
将条件$dp(j)\leq \operatorname{sum}(j - 1) - \operatorname{sum}(i - 1)$转化为$\operatorname{sum}(j - 1) - dp(j)\geq \operatorname{sum}(i - 1)$

则如果存在$k < j$，且
$$
\operatorname{sum}(k - 1) - dp(k) > \operatorname{sum}(j - 1) - dp(j)
$$
则$j$为无用决策。单调队列维护。
单调队列左端点维护最小的$\operatorname{sum}(j - 1) - dp(j)\geq \operatorname{sum}(i - 1)$
右端点维护$\operatorname{sum}(j - 1) - dp(j)$递减

BZOJ 3994
题意：设$d(x)$为$x$的约数个数，给定$n,m$, 求
$$
\sum_{i=1}^n \sum_{j=1}^m d(ij)
$$

首先知道结论
$$
d(ij)=\sum_{a|i} \sum_{b|j} [\gcd(a,b)=1]
$$
具体可以通过展开唯一分解式子，根据 $gcd$ 性质，然后得出两个式子等价。
然后原答案可以化为
$$
\sum_{i=1}^n \sum_{j=1}^m \sum_{a|i} \sum_{b|j} [\gcd(a, b)=1]
$$
将$a,b$放到前面，并且改成$i,j$
$$
\sum_{i=1}^n \sum_{j=1}^m \lfloor \frac ni \rfloor \lfloor \frac mj \rfloor [\gcd(i, j)=1]
$$
设
$$
f(k)=\sum_{i=1}^n \sum_{j=1}^m \lfloor \frac ni \rfloor \lfloor \frac mj \rfloor [\gcd(i, j)=k] \\
g(k) = \sum_{i=1}^{\lfloor \frac nk \rfloor}f(ki) \\
$$
则
$$
g(k) =\sum_{i=1}^n \sum_{j=1}^m \lfloor \frac ni \rfloor \lfloor \frac mj \rfloor [k|\gcd(i, j)]
$$
将$k$提出来
$$
g(k) =\sum_{i=1}^{\lfloor \frac nk \rfloor} \sum_{j=1}^{\lfloor \frac mk \rfloor} \lfloor \frac n{ik} \rfloor \lfloor \frac m{jk} \rfloor
$$
由反演，得
$$
f(1)=\sum_{d=1}^n \mu(d) \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{j=1}^{\lfloor \frac md \rfloor} \lfloor \frac n{di} \rfloor \lfloor \frac m{dj} \rfloor
$$
设$g(n)=\sum_\limits{i=1}^{n} \lfloor \frac ni \rfloor$，那么
$$
f(1)=\sum_{d=1}^n \mu(d) g(\lfloor \frac nd \rfloor) g(\lfloor \frac md \rfloor)
$$
预处理$g(n), \mu(n)$的前缀和，即可整除分块得到$O(T\sqrt n)$的复杂度

bzoj 3124
题解：对于给定的一棵树，求其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

第一问直接两次 DFS 求直径。
考虑第二问求直径必须边。
记录

$Ldis$: 从直径左边端点到直径右边点的距离
$Rdis$: 从直径右边端点到直径左边点的距离
$Edis$: 直径上的点的最大偏心距

我们从一个直径端点在直径上开始往右走，若存在$Rdis(i)+Edis(i)=len$，$len$为直径长，那么这里开始后面的就不是必须边。

然后相反地，我们从右往左做一次，然后得出了一个范围$[l,r]$，然后就非常好处理了

Bzoj 2154
题意：给定$n, m$，求
$$
\sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i, j)
$$

化为$\gcd$式子
$$
\sum_{d=1}^n d \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{\gcd(i,j)} \\
\sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac nd \rfloor}\sum_{j=1}^{\lfloor \frac md \rfloor}ij \cdot [\gcd(i,j)=1]
$$
设
$$
f(n,m)=\sum_{i=1}^n \sum_{j=1}^m ij \cdot [\gcd(i,j)=1] \\
=\sum_{d=1}^n \sum_{d|i} \sum_{d|j} \mu(d) \cdot d^2 \sum_{i=1}^{\lfloor \frac nd \rfloor}\sum_{j=1}^{\lfloor \frac md \rfloor}ij
$$
设 (两个等差数列相乘)
$$
g(n,m)=\sum_{i=1}^n \sum_{j=1}^m ij =\frac{n(n+1)}{2} \times \frac{m(m+1)}{2}
$$
则
$$
f(n,m)=\sum_{d=1}^n \mu(d) \cdot d^2 \cdot g(\lfloor \frac nd \rfloor, \lfloor \frac md \rfloor)
$$
即原式为
$$
\sum_{d=1}^m d \cdot f(\lfloor \frac nd \rfloor, \lfloor \frac md \rfloor)
$$

计算$f(n,m)$时整除分块，计算答案时整除分块，时间复杂度$O(n+m)$

Codeforces 1011D
题意：给出一棵有根树，对于每个节点$x$，定义一个无穷序列$d$，其中$d(x,i)$表示以$x$为根节点的子树中到$x$的距离恰好为$i$的点的个数，$i \in [0， INF]$，现在对每个点$x$，希望求出一个东西$j$，使得对于任意$k < j$，$d(x,k) < d(x,j)$，对于任意$k > j,d(x,k) \leq d(x,j)$

本题类似于CF600E
其实就是对每个点求出这个点子树的的某层节点最多的那层。
考虑将层作为颜色，维护子树中颜色最多的那个颜色。
那么这里没有修改，并且也是子树操作，那么我们可以考虑用树上启发式合并。
也就是将树轻重链剖分(求出重儿子)，然后对于每个点，先遍历所有的轻儿子子树，然后再回退所有当前答案，然后遍历重儿子子树，不回退答案，然后再直接遍历所有的轻儿子子树，不回退答案，并且不管下面的轻重链了。
那么这题就是一个裸题了，注意用map方便。
更新答案方式类似莫队。
复杂度证明：
引理1：

根节点到树上任意节点的轻边数不超过$\log n$条。

证明：我们设根到该节点有$x$条轻边, 该节点的子树大小为$y$，显然轻边连接的子节点的子树大小小于父亲的一半（若大于一半就不是轻边了），则 $y < n/2^x$，显然$ n > 2^x$所以 $x > \log n$

一个节点的被遍历的次数等于他到根节点路径上的轻边树$+1$

证明：显然，只要上面有一条轻边下面才会被遍历一次

综上，时间复杂度大约为$O(\log n)$