模拟赛
T1
首先是曼哈顿距离到切比雪夫距离的转化，到原点曼哈顿距离为定值 $a$ 的点组成的图形为一个斜正方形，且原点到顶点的距离为 $a$，正方形边长为 $\sqrt{2} a$ ，而到原点切比雪夫距离为 $a$ 的点组成的图形为正正方形，且边长为 $2a$，那么我们可以通过把平面坐标系旋转 $45$ 度，并把边长乘上 $\sqrt 2$ 即可。反映在坐标上，即做坐标变换 $(x,y)\rightarrow (x-y,x+y)$，然后利用切比雪夫距离的横纵坐标差去最值来优化我们找的过程。
根据以上分析，所以对于每个点来说，分别在左上左下右上右下 $4$ 个方向曼哈顿距离最大的点在一条直线上。
介绍一下 Borvka 算法，大致思路是找到每个点距离其最远的点，然后连边，这样做联通块个数减少一半，至多要做 $\log n$ 轮，所以复杂度是 $(n+m)\log n$，其中 $n$ 为点数 $m$ 为边数。而对于这个题，做完一遍这个算法后，至多为有 $4$ 个连通块剩余，所以我们对这 $4$ 个集合枚举最大边连接即可，由于这些连边至少会有一个顶点为我们选定的 $4$ 条直线上的点，所以我们直接枚举的复杂度是 $O(n)$ 的。
注意，直线上选哪个点都行。
赛时写了个巨麻烦的树状数组 $n\log n$ 扫描线做法。
代码：
1 |
|
T2
首先考虑如果从 $i,j$ 建一条 $0$ 边，表示 $i<j$，建一条 $1$ 边表示 $i\le j$，我们可以得到一张 DAG，在 DAG 上 DP 显然不是很好做的，因为限制不够紧，考虑这张图是否可以缩进限制，使其变成一棵树？
有一个关键性质：区间之间只可能包含不可能相交，根据这个我们可以简单证明原 DAG 一定可以缩成一棵树。在树上 DP 用前缀和优化到 $O(nm)$ 即可。
1 | struct edge{ |
T3
首先考虑后缀自动机，因为后缀自动机存储了所有子串的信息，那么对于一个状态，里面除了最长的那个字符串，其余字符串一定是不重要的，而如果一个状态有至少两个转移，那么这个状态里最长的那个串一定是重要的，因为在这个串前面加字符得到的字符串在别的状态里，$endpos$ 集合不一样，而往后加一个字符有不同加法，所以一定也不一样。
如果一个状态没有转移，即 $last$ 这个状态，里面最长的串一定也是重要的，而对于只有一个转移的状态，如果它是后缀，那么也是重要的，因为它往后加字符之后得到的串的 $endpos$ 一定不和原来一样。如果一个状态里面最长的字符串是重要的，那么我们称这个状态也是重要的，我们需要统计所有重要的状态，和在 $fail$ 树上，从根到 $last$ 这个路径上所有不重要的状态的个数之和。前一个好统计，后一个不好统计。因为树的形态会变化，所以一种思路是我们用 LCT 去维护 fail 树，操作就是在一个边上加上一个点，以及给一个点加一个叶子。
不过 LCT 常数太大了，只能做 $10^5$，切队长直接魔改了 LCT 过掉了这个题，我们考虑倒过来做，从后向前做，这样我们就可以近似认为树的状态没有变化，而我们需要维护每个点是否重要，以及一个点到根不重要点的数量，操作相当于树上单点改，链求和，树状数组树上差分做就可以。注意操作数是 $O(n)$ 的，因为改变次数和转移数和节点数是同一级别的。
代码：
1 | int n,ans[N]; |