类型系统

作者：Luca Cardelli

英文原文 PDF：Type Systems。

题面

给定一个长度为 $10^5$ 的字符串，求同构意义下的本质不同子串数。

分析

考虑如何求一个串的本质不同子串数，实际上对他求一个后缀数组和 height 数组即可，进一步转化我们只要能对求出两个后缀的 LCP 长度，就能实现后缀排序。

将同构转化为距离上一次出现该字符的距离，可以发现每个后缀和整体的差别仅有 $26$ 个开始位置。

我们现在考虑如何求两个后缀的 LCP，首先两个字符的情况可以参考 2020 牛客暑期多校训练营第 1 场 A，我们将其扩展到更大字符集。

我们将这个串，用每种字符的第一次出现位置分割开来。如果两个串同构，那么这些位置必然也是一一对应相同的。

求 LCP 时，只需要一段一段考虑即可。

题面

给定一个长度为 $n$ 的数组，对于所有子数组求最大子段和。

其中 $2 \le n \le 10^5$。

分析

考虑分治，也就是需要统计跨越中点 $m$ 的贡献。

注意到，跨越中点的区间的最大子段和位置，它要么完全在左半边，要么完全在右半边，要么是中点往左右延申得到的。

我们在区间 $[l,m]$ 枚举左端点的位置，可以发现右端点从左往右移动的过程中：首先是一段使用完全在左半边，然后是一段左右拼接，最后是完全在右半边。

二分出 $2$ 个边界的位置即可。

题面

给定一棵 $n$ 个点的有根树，初始时，每个点处于上班状态，你现在需要构造一个操作序列，使得每个点都满足一次，一个点满足当且仅当只有这个点的子树在上班，其他全在下班。

操作序列会维护一个栈结构，分为 $3$ 种操作：

1. 点 $u$ 下班，加入栈中；

2. 栈顶 $u$ 弹栈，$u$ 重新上班；

3. 报告点 $u$ 处于满足状态。

其中 $2 \le n \le 10^5$，操作序列长度不超过 $9 \times 10^6$。

分析

对于一棵大小为 $n$ 的树，我们可以选择一条链（不妨选择重链），不断将外部的点删掉，可以用 $n$ 次操作，由浅到深将整条链都满足一次。之后，这条链就不在有用了，并且把树划分为一个森林，有多个等价的子问题。

思考一些暴力的做法，留下一棵树，其他入栈，对这棵树递归构造完成后（递归后满足子树所有点在栈中），需要去弹出下一个子问题的树，因为是栈结构，所以需要弹出栈顶的两棵树，再将做好的树入栈，以此类推。显然，这样一开始做的树就会被反复加入和弹出，不够优。

不妨使用哈夫曼编码以子树的大小作为频率值进行合并，在构造好的哈夫曼树上递归构造即可。由于哈夫曼编码的性质，每个点深度频率乘积的和，大约为 $O(n \log n)$ 级别，可以通过本题。

A Circle Coloring

每个点有 $3$ 种选择，一个点需要与前后不同，显然遍历一遍即可。

B Arrays Sum

注意到，每种数有多个并没有用，假设一共有 $n$ 种数。

考虑 $k=2$ 的时候情况，如果 $n \le 2$，那么一次操作就能完成，否则之后每次前面一部分填 $0$，然后构造下一个数。

因此 $k>2$ 也是类似的，第一步制造 $k$ 个，然后每次制造 $k-1$。

C Discrete Acceleration

直接对着题意模拟即可。

D Searchlights

注意到，被控制的区域呈现一种下降台阶的形状。于是，每个人，要么往上走，要么往右走，要么走到某个拐角处。

于是，每个人有很多种选择 $(x_j,y_j)$，表示他两个方向需要的步数。

按 $x$ 从小到大枚举，如果所有人都满足过了，在所有人 $y$ 的最小值，取最大值。

E Avoid Rainbow Cycles

注意到，对于每个集合，不需要真的搞出最大团，只要按顺序连成一条链，如果这个图有环，那么原图必有环。

因此题目要求的是，删除最小的边，使得原图没有环，也就是加入最多的树边。

做一个类似 MST 的过程即可。

F Two Different

考虑 $n=2^k$，我们可以每次将数组对半分，如果左右半边都分别被弄成了同样的数，那么我们通过左右两边一一对应，就能将整个区间弄成同一个数。

进一步，考虑 $n$ 的最高位，类似 ST 表，做两次即可。

G Clusterization Counting

给定一个无向带权完全图，每条边边权不同，求有多少种点集的划分方案，使得每个团内的所有边权小于该团所有向外的出边。

观察 Kruskal 建最小生成树的过程，每次合并两个连通块，新加入那条边的权值一定大于两个连通块内的所有边，于是我们可以合并两个连通块的 dp 值。

合并 dp 值只需要做一个类似卷积的过程即可。

特别地，如果某个连通块本身就是 $1$ 个团，那么其分成 $1$ 块的方案数 $+1$。

具体实现可以构造一棵 Kruskal 重构树，做树形背包的 dp。