简要题意

给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式：

• 长度不同时，长度短的排在低次位。
• 长度相同时，按字典序排序。

简单而言，长度是第一关键字，字典序是第二关键字。现在给定 \(Q\) 个询问，每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。

数据范围

\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)

主要思路

先差分，然后再来做这个不相交子串匹配的问题。

我们可以考虑用线段树来维护 endpos 集合，然后用启发式合并的方式来计算一个后缀点与当前点集之间产生的贡献。有两种情况：

• 当前为 endpos 的最长长度、与当前位置 \(x\) 不相交的子串。这个可以直接暴力线段树上查个数。
• 长度小于 \(maxdep\)，以 \(endpos\) 在左边的情况为例：答案的贡献就是 \(x – endpos – 1\)。

主要思路

看完题面就知道应该又是传统的字符串重工题，最后写了我 6.3KB。

首先建出 SAM 然后处理倍增+线段树维护 endpos 集合是显然需要的。然后开始考虑这个二元组的含义。

想了一段时间如何正着算，发现这个东西成立的条件是或，所以正着算只能用子集容斥。所以我们考虑把条件进行反转，变成强与形式，然后用所有的二元组的数量 \( {n – 1 \choose 2} \) 来减掉即可。

如何算正好不符合条件的二元组数量呢？分两种情况讨论：

• 最左区间和最右区间相交
• 最左区间和最右区间不相交

主要思路

这个题读完之后大概能知道是要建一个反串的 SAM，然后通过倍增定位 \(A, B\) 串然后加边，找最长路即可。

但是发现直接这样做，碰到 \(|A| < |B|\) 的时候会 GG，因为可能会出现在同一个节点上。这个时候我们就通过长度进行排序，给被重复的节点多做几个影子节点即可。