比赛链接

Solved by nikkukun.

水题不表。

Upsolved by nikkukun.

定义 $f(S, x, y)$ 是一个长度为 $y - x + 1$ 的串，且字符依次为 $S[x:x]$ 的最大值、$S[x:x + 1]$ 的最大值……$S[x : y]$ 的最大值。求 $f(f(S, x_1, y_1), x_2, y_2)$ 有多少种本质不同的串，其中 $[x2, y2] \subseteq [x1, y1] \subseteq [1, n]$。

显然 $f(S, x_1, y_1)$ 必然是个串中字符递增的东西，然后递增东西里取 $f$ 等于原串，故相当于问所有 $f(S, x_1, y_1)$ 有多少种本质不同的子串。同时枚举每个位置 $x$，发现实际上只需要求 $f(S, x, n)$，而其他 $f(S, x, \ast)$ 都是它的一个子串。因此，可以利用序列自动机求出 $f(S, i, n),\ i = 1, 2, \ldots, n$，这 $n$ 个串本质不同的子串个数就是答案。

注意到这样的串可以用一个十元组唯一表示，因此可以枚举子串的开头结尾字符分别是十元组的哪两个位置，并按照这两个位置中间的子元组进行分类，计算出对一段中间固定的子元组，向左右添加字符可以构成什么串。这个问题相当于求二维平面上一些点向左下构成的矩形中，一共覆盖了多少个整点。

这里在比赛时写得非常混乱，是因为没有处理好边界重复的情况。如果设定好加在两端的字符都至少有一个，则这样子并不会出现重复（需要额外加上开头结尾是同一段的贡献）。另外，可以用 `vector` 做 key 方便代码编写。

总时间复杂度 $O(\Sigma ^2 n \log n)$，勉强能过。

参考解题思路 1，如果能把 $f(S, i, n),\ i = 1, 2, \ldots, n$ 全插到 SAM 里，那就能直接求答案，可惜字符串长之和是 $O(n^2)$ 的。

考虑倒序建 trie。在 trie 上行走时，一旦有某个字母被新插入的字母更新了，则 trie 上会从原点向右多出来一条仅有一种字母的新链。对于每个位置而言，它只会被这样向右移动到新链上 $O(\Sigma)$ 次，故 trie 中最多 $O(\Sigma n)$ 个节点，于是可以跑广义 SAM 了。

总时间复杂度 $O(\Sigma ^2 n)$。

Solved by nikkukun.

有平行线 $AB \parallel CD$ 或 $AB \parallel DC$，给出 $AC, AD, BC, BD$ 的长度，判断是哪种情况。

可以先判断 $C$ 和 $D$ 在 $AB$ 中线的哪一侧，然后分类讨论。标程的做法是 $AB \parallel CD$ 当且仅当 $AD$ 或 $BC$ 为四边中的最大值。