BZOJ 1562
题意：初始有一个序列$[0,n-1]$升序排列$a_i$，然后给出每个位置的$D=\min(∣T_i−a_i∣,N−∣T_i−a_i∣)$，然后你要找到一组字典序最小的方案$T_i$
显然一个$a_i$对应两个$T$: (i + d) % n + 1, ((i - d) % n + n) % n + 1
构造二分图，左边是$a_i$，右边是$T$，连边，就是求一个最大匹配。
但是匈牙利求不一定字典序最小，我们强制让匈牙利先连序号小的点，这样是不是对的呢？
答案是否定的，因为后面不能匹配就会动到前面的匹配，这样就不最优了。
其实可以倒过来求匈牙利，这样就能保证前面的要最小边能够从后面的修正得到。具体证明可以参见NOI 2009 变换序列 - BYVoid，本文下面也搬运了一份。
这题其实类似于Luogu 2526，都是一个位置有多个选择，并且这些选择都是一个集合的，然后就可以考虑二分图最大匹配。
其实这类问题写暴力时就会发现时间复杂度瓶颈于多个选择。
知识点
原来$0$的改为$1$时注意!x的判断修改
BZOJ 1576
题意：给定一张$n$点$m$边无向图，请你找出$1 \to n$不经过$1 \to n$的最短路的最后一条边的最短路。保证最短路唯一
保证最短路唯一，那么构造最短路树。
接着最短路树上就是最短路，考虑非树边才能得到答案。
对于每条非树边$u,v$，他加入树就形成了环，这个环$u,v$上所有点(除了$\text{LCA}(u,v)$)都可以得到一个新的路径长，即为$dis(u)+dis(v)+W_{u,v}-dis(i)$，发现这个答案只与这条边有关，所以我们可以直接按这个排序，然后从小到大枚举非树边$u,v$，更新环上没更新的点。
这里可以树剖+线段树维护，但是有最方便的方法：
没更新的点更新明显是一个合并的过程，用并查集维护即可。类似倍增跳LCA/树剖的方法来合并
知识点
保证最短路唯一：最短路树
并查集妙用
不要开小关于边的数组
BZOJ 3669
题意：给定$n$点$m$边无向图，每条边有一个边权$(a, b)$，能经过某条边当且仅当当前的$A \leq a, B \leq b$，试确定$A,B$，使得能从$1$走到$n$。
第一眼以为二分套二分，但是这题二分后再二分没有单调性了…但是还是能拿到$65$分
贪心两者和最小：将前者排序后，在不大于前者的情况下，让后者尽量小。
那么将边按照$a$排序，然后我们想想怎么样能让$b$最小。
显然一条路径最长边最小的路径在当前图的最小瓶颈生成树上，那么这里就是动态维护一个最小生成树
即，若两点不连通，则直接连边；否则将路径上的最大边删除加入这条边(或者这条边比较小不用动任何东西)
那么 LCT 维护路径。注意重边和自环。
这里边权可以变成点权，是个经典套路
注意Splay后所有的信息都不能再用之前的，变量改变后不要再用，要留意变量是否会在中途改变，会的话开临时数组存储 (特别是用了一个值之前调用了一个函数，这个函数可能改变这个值)！！！
知识点：
1、边权变点权 (网络流常用技巧)
2、Splay后所有的信息都不能再用之前的，变量改变后不要再用，要留意变量是否会在中途改变，会的话开临时数组存储 (特别是用了一个值之前调用了一个函数，这个函数可能改变这个值)
3、贪心两者和最小：将前者排序后，在不大于前者的情况下，让后者尽量小。
4、注意重边自环
BZOJ 4650
题意：如果一个字符串可以被拆分为 $AABB$ 的形式，其中 $A$ 和 $B$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。
本题直接无脑Hash有85分，思考一下，可以发现$AA$和$BB$本质上相同，只需要统计每个位置向左向右可能有几种$AA$串，乘法原理即可。这个Hash有95分。(发现这个方法我还是用后缀数组想的时候推出来的，但是没想出后缀数组做法没有回来用Hash暴力…)
后缀数组做的话也要用到上面的方法，考虑枚举$AA$串的$len$，然后在字符串上每$len$个字符作一个「关键点」，可以发现每个当前$AA$串必过两个「关键点」。
考虑两个「关键点」。假设$LCP$是这两个「关键点」的最长公共前缀，$LCS$是这两个「关键点」的最长公共后缀(不是最长公共子序列)，那么
当$LCS+LCP \leq len$时
当$LCS+LCP \geq len$时
Bzoj 1049
题意：现在我们有一个长度为$n$的整数序列$A$。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
第一问即经典问题。考虑不严格上升的序列，则为$n-LIS$，(这里的$LIS$为不下降的)
严格上升，则说明$i-j \geq a_i-a_j$，不然这个区间不可能严格上升。
移项，则$i-a_i \geq j-a_j$，那么将原来的$a_i$变为$a_i-i$按照同样方法处理即可。
对于第二问，我们设$f(i)$为$[1,i]$的答案，则
$$
f(i)=\max\limits_{dp(j)+1=dp(i)}(f(j)+w(j+1,i))
$$
那么我们怎么计算$w$呢
我们可以发现对于任意区间$[i,j]$都$\exists k$使得$[i,k]=a_i$, $[k+1,j]=a_j$，并且一定$\exists k$使得其为最优策略
那么对于每个$w$暴力$k$的位置。由于数据随机，所以$i$的的决策点$j$很少，复杂度跑不满
注意代码细节，加上前后最小值最大值方便操作
BZOJ 3675
题意：你正在玩一个关于长度为 $n$ 的非负整数序列 $a_i$ 的游戏。这个游戏中你需要把序列分成 $k+1$ 个非空的块。为了得到 $k+1$ 块，你需要重复下面的操作 $k$ 次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
引理：
最终答案和分割顺序无关。
证明：若分了$3$块，设为$a_1,a_2,a_3$
则
$$
a_1 a_2 + (a_1+a_2)a_3 = a_2 a_3 + (a_2 + a_3)a_1
$$
所以两者等价，并且容易扩展到更多块的情况。并且答案是$a$两两相乘的和(或者是$a_1 + (a_1+a_2)a_3 + (a_1+a_2+a_3)a_4 +\dots + (a_1+a_2+ \dots + a_{k-1})a_k$)
那么设$dp(k,i)$为前$i$个分了$k$次的最大值。根据上面的式子，可以有DP方程
$$
dp(k,i)=\max(dp(k-1, j)+s(j) \cdot (s(i) - s(j)))
$$
其中$s(i)$为前缀和。
显然可以斜率优化。
BZOJ 2754
题意：见上。
考虑将所有名字姓和名用特殊符号链接，然后构造后缀数组
引理1：
$S_2$ 是 $S_1$ 的子串当且仅当 $\exists S_1$的后缀和$S_2$的$height=len(S_2)$
引理2：
后缀数组的$SA$数组具有二分单调性，即确定了前$i-1$位，可以在$SA$数组中二分第$i$位的位置
用引理1或者引理2(代码使用2)用上二分可以找出一个询问在$SA$数组上的区间范围，即这个区间上的后缀的前缀都有这个询问串。
这里二分要用左闭右闭区间的，用左闭右开会莫名GG
那么现在问题转化为求区间的不同颜色的个数，显然莫队裸题。
第二问的话，在莫队的时候，如果第一次加入某种颜色，则加上当前最大可能的个数，然后某种颜色被完全删除后就减掉当前最大可能的个数
BZOJ 3527
给定$n, q_i$, 求
$$
E_j=\sum\limits_{i=1}^{j-1} \frac{q_i}{(i - j)^2} - \sum\limits_{i=j+1}^{n} \frac{q_i}{(i - j)^2}
$$
设$f(i)=q_i, g(i)=\frac 1{i^2}$
则
$$
E_j=\sum\limits_{i=1}^{j-1} f(i)g(i-j) - \sum\limits_{i=j+1}^{n} f(i)g(i-j)
$$
因为$g(i)$为偶函数，则
$$
E_j=\sum\limits_{i=1}^{j-1} f(i)g(j-i) - \sum\limits_{i=j+1}^{n} f(i)g(i-j)
$$
那么前面是一个卷积形式，后面可以翻转$f(i)$后变为另一个卷积形式，FFT 计算即可。
Bzoj 2733
题意：维护一个无向图，有两种操作：
B x y 表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。Q x k 表示询问当前与岛 $x$ 连通的所有岛中第 $k$ 重要的是哪座岛，即所有与岛 $x$ 连通的岛中重要度排名第 $k$ 小的岛是哪座，请你输出那个岛的编号。这题一开始看见连边以为是$LCT$，但是这题不断边，所以直接并查集维护即可。对于每个联通块开一个 Splay 处理第 $k$ 大即可，这里值域小也可以开权值线段树，更加方便。
合并则使用启发式合并，复杂度为$O(n\log n)$，注意代码实现细节
知识点
1、Splay有时候值域小也可以开权值线段树，更加方便
BZOJ 2002
题意：见上。
如果没有修改就是个递推……
有修改的话我们将这个递推状态抽象成图论的点，然后发现这是一棵树
然后修改相当于断边连边，那么就是 LCT 裸题了。
这题也可以分块，每个块维护
知识点
1、递推/DP等状态抽象成图论的点，树、DAG图等