Codeforces 1082E
题意：给一个长度为$n$的序列，并且确定一个数$c$。你可以任选一个区间$[l,r]$, 对该区间$+k,k$可以为负数，使得最后的$n$个数中，等于$c$的数字的个数最多。问最多有多少个这样的数？

方法1
将所有数减去$c$，则答案就变成最后最多几个0.
然后如果是整个区间加减的话答案就是出现次数最多的数的个数。
现在是区间，分析一下发现其实和上面类似，只需要考虑一下多余的0怎么处理
考虑 22002 这个数据，这个数据如果将2减去则会破坏中间的0，那么如果操作这个区间对答案贡献为 $3-2=1$ 。那么我们发现，算出序列 0 的个数，然后扫一遍这种情况的区间就行了。
我们分颜色讨论，一个颜色肯定取的块是连续的(前缀、后缀、中间一段)，那么我们可以像DP求最大字段和一样，如果前面的答案为负了，那么舍弃重新开始。对每个颜色进行这个操作即可。

方法2

Codeforces 1081D
题意：给定$n$点$m$边无向连通图，一条路径长度定义为其边的最大值，两个点之间的距离为他们之间最短路径长度。现在给$k$个特殊点，请对每个特殊点找到另一个最远的特殊点，输出距离。
根据距离的定义，求出原图的最小生成树(最小瓶颈生成树)，树上两点的唯一路径就是两点距离。并且所有两两点之间的距离最大值是某一条边的边权。
那么我们根据边权从小到大枚举每条树上的边来判断是否能成为这条边。这条边应该在$k$个点组成的虚树上。但是并不用那么麻烦，对于每条边判断他左边是否有特殊点，右边是否有特殊点，都有这条边才有可能成为这条边，否则不可能有任意一条路径经过该边。
根据连通图和相关性质观察发现，最后答案都是一样的。

Codeforces 1093C
题意：给出数列$b_i​$, 已知一个序列$\forall i, a_i+a_{n-i+1}=b_i​$且$a_i \leq a_{i+1}​$，请构造出一个合法$a_i$数列，保证至少有一组解。
解：这个保证至少有一组解提示我们要最优化构造。
最优就是前面尽可能小，后面尽可能大。
所以我们让$a[0]=0, a[n+1]=INF$，然后根据升序约束求出$a[1, n/2]$的值, $a[n/2+1,n]$则为$b[i]-a[i]$

Codeforces 1093D
题意：给出$n$点$m$无向边图，请给每个点赋点权$1,2,3$，使得$\forall (u,v) \in E，w_u+w_v$为奇数。求方案数模$998244353$
解：对于一条边和要是奇数，那么点权一奇以偶。那么对图二分图染色，不同颜色的点分类赋奇数还是偶数，注意图不连通。最开始我把所有点一起算了贡献，直接爆炸。要分开乘法原理算。

Codeforces 1093G
题意)：给你 $n$ 个 $k$ 维的点 $a_{1..n}$，定义两点$(x_1,x_2,\cdots,x_k),(y_1,y_2,\cdots,y_k)$间的曼哈顿距离为 $\sum_{i=1}^k|x_i-y_i|$。
你需要执行下面两种操作：
$1 i b_1 b_2\cdots b_k$，表示将 $a_i$修改为 $(b_1,b_2,\cdots,b_k)$。
$2 l r$，表示询问 $[l,r]$ 内最大的两点间曼哈顿距离，即任取 $x,y\in[l,r]$ 得到的所有曼哈顿距离中的最大值。
翻译来自Luogu

对于绝对值式子，不好处理我们作一个变式。
考虑二维的情况，设点$(a_1, a_2), (b_1, b_2)$，则根据绝对值函数定义和$x \leq |x|$，有
$$
|a_1-b_1|+|a_2-b_2| \\
= \max (a_1-b_1, b_1-a_1)+ \max (a_2-b_2, b_2-a_2) \\
= \max (a_1-b_1+a_2-b_2, a_1-b_1+b_2-a_2, b_1-a_1+a_2-b_2, b_1-a_1+b_2-a_2) \\
= \max ((a_1+a_2)-(b_1+b_2), (a_1-a_2)-(b_1-b_2), (-a_1+a_2)-(-b_1+b_2), (-a_1-a_2)-(-b_1-b_2))
$$

观察到符号是+和-的$2^d$种不同组合，所以我们设第$i$个点的第$j$种为$s(i,j)$，那么两点曼哈顿距离最大值就是
$$
\max_j \max_i(s(i,j)-s(i,j))
$$
变形得
$$
\max_j (\max_i(s(i,j))-\min_i(s(i,j)))
$$

那么用线段树维护$\max_is(i,j)$和$\min_is(i,j)$即可。

知识点：
以后遇到绝对值$\max \min$式子要尝试拆一下，因为很多这样的式子是不方便直接处理的，要转化一下。

Bzoj 1150
题意：见上。
很容易发现最优配对一定是相邻的，因为反应序列数据相对关系的是差分序列，所以我们在差分序列上找$k$个最小和不相邻点即为答案。

现在问题就是直接取最小值可能没有取最小值两边的数更优，那么我们可以先取最小值，然后之后考虑怎么反悔。参照低买高卖那题，那题先买，如果后面有更优的，那么在这个基础上继续买卖可以得到最优解。这里先取了最小值，那么如果不优，最小值两边的数一定必取，因为如果只选一边选最小值最优。我们要添加一个元素在中间，使得之后选这个点相当于返回选了两边的数。那么用链表支持这个操作。由于是全局最小值，很容易发现可以用堆来维护最小值，注意堆和链表要同步，相当于映射关系。

注意链表有误，要将第一个点插在 $h$ 后面

BZOJ 4407
题意：
给定$n,m,k$，求
$$
\sum_{i=1}^n\sum_{j=1}^m \gcd(i,j)^k \mod (10^9+7)
$$

按照套路反演以后得到

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

此时我们发现可以分块套分块达到复杂度$O(n)$单次询问。
但是还是不够，那么继续变形

设$T=di$，则

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

设$f(T)=\sum_{d|T}d^k \mu(\frac Td)$，发现$d^k$和$\mu(k)$都是积性函数，所以乘积也是积性函数，所以我们可以线性筛$O(n)$算这个积性函数值。

如何线性筛？
线性筛积性函数考虑两个
第一个是$f(p), p$为质数时的取值怎么$O(1)$算
第二个是$f(p^x), p$为质数时的取值怎么$O(1)$算，也就是说我们需要从$f(p^x)$转到$f(p^{x+1})$怎么求

考虑将$T$质因数分解，那么对于每个$p_i$

$$
f(p_i^{x_i})=\sum_{d|p_i^{x_i}}d^k\mu(\frac{p_i^{x_i}}d)
$$

因为有$\mu$的存在，只需要考虑$d=p_i^{x_i}$和$d=p_i^{x_i-1}$的情况，则原式化为

$$
f(p_i^{x_i})=\mu(p_i) \cdot p_i^{k(x_i-1)} + \mu(1) \cdot p_i^{x_ik}
$$

即

$$
f(p_i^{x_i}) = p_i^{x_ik} - p_i^{k(x_i-1)}
$$

$$
f(p_i^{x_i}) = p_i^{k(x_i-1)}(p_i^k-1)
$$

这个式子可以方便解决$f(p^x), p$为质数时的取值

对于第一个，$f(p)=\mu(1) \cdot p^k + \mu(p) \cdot 1^k=p^k-1$

那么这样就可以线筛了。

Bzoj 2152
题意：询问树上距离为$3$的倍数的路径条数。

直接上点分治，算答案的时候用桶存答案，然后乘法原理即可。
是 $ k $ 的倍数相当于模 $ k $ 为 $ 0 $

模板及讲解

点分治

点分治就是处理树上路径的一个树上分治算法。
其基本思路与分治类似。

模板题

Poj 1741

给出一颗无根树，求树上距离小于等于 $k$ 的点对(路径)有多少个。
$n \leq 10000$

基本思路

点分治基本步骤：
1、DFS 每一棵子树 (以重心为根保证复杂度)
2、对当前 DFS 的子树进行求值 (calc)
3、求值完删除当前重心继续往下 DFS 子树，顺便对子树进行求值后容斥

求值方法 (因题而异，用 Poj 1741 为例)：
1、DFS 求出所有连通点到当前子树根的距离
2、将距离排序，用两点法等对信息进行处理

点分治核心函数是 calc

代码实现

函数

• void dfs(int u)：DFS 求解子树，根为 $u$
• int calc(int u, int D)：计算以$u$为根子树的答案，$(fa[u], u)$边权为$D$
• void dfsD(int u, int D, int fa)：计算以$u$为根子树节点到 $u$ (根)的距离数组，$D，fa$为临时局部变量
• void getRt(int u, int fa)：求解以$u$为根的子树的重心
  阅读全文 »

bzoj 3032

一行之间交换不会影响这一行的摊点数，列同理。
所以行列分开独立处理。

那么现在就是要对行列分别求，最小交换次数使得每个位置摊点数相同。
这个很像均分纸牌，我们可以发现就是均分纸牌，而这里加上了环形。

我们可以发现环形均分纸牌中一定有两个人之间没换过纸牌，那么用朴素方法就是枚举这个位置将链断环成链。

我们想一想均分纸牌的本质，就是当前所有数减去平均数之后$[1,i]$的前缀和一定要是0.
而现在不是从1开始，经过类似分析和问题有解必然有$[1,n]$的前缀和为0可以发现，我们所求答案就是
$$\sum_{i=1}^n |S_i - S_k|$$
我们发现这个是中位数的性质公式，则$S_k​$为中位数，免去枚举。

BZOJ 2705
题意：求
$$\sum_{i=1}^n gcd(i,n)$$

解：
$$\sum_{i=1}^n gcd(i,n)=\sum_{d|n} d \sum_{i=1}^n [gcd(i,n)=d]=\sum_{d|n} d \sum_{i=1}^{\lfloor \frac nd \rfloor} [gcd(i,\lfloor \frac nd \rfloor)=1]=\sum_{d|n} d \cdot \varphi(\lfloor \frac nd \rfloor)$$

枚举$d|n$计算即可。单个$\varphi(n)$可以质因数分解在$O(\sqrt n)$时间求得。

时间复杂度的计算：
枚举因数$d|n$: $O(\sqrt n)$
求因数的$\varphi(d)$: $O(\sqrt {\sqrt n})$
综上复杂度为$O(n^{\frac 34})​$ (刚开始以为这个是$O(n)​$的不敢写就挂了……)