Solution - Atcoder ABC280Ex Substring Sort

对于这种子串问题，且有多个基础串，一个比较直观的想法就是先上个广义 SAM。

考虑 SAM 与字典序如何联系上。
因为跳 \(\operatorname{fail}\) 相当于是删除子串的一个前缀，直接这样子明显是不行的，因为跳了 \(\operatorname{fail}\) 字典序没有一个很直观地表示。
但是反过来考虑反串，那么在反串上跳 \(\operatorname{fail}\) 就相当于是删除后缀了。
发现这似乎就能联系上了。

下面一部分指的字符串就是反串中对应的字符串。

建出来 \(\operatorname{fail}\) 树，节点 \(u\) 的儿子 \(v\) 按照 \(s_{v, \operatorname{len}(u) + 1}\) 排序即可（\(s_v\) 指 \(v\) 节点对应的字符串），就相当于是确定好了 \(u\) 的儿子字典序大小的相对顺序。
这里的正确性是考虑不会存在 \(u\) 的儿子 \(a, b\) 满足 \(s_{a, \operatorname{len}(u) + 1} = s_{b, \operatorname{len}(v) + 1}\)。

那么对于 \(\operatorname{fail}\) 树跑出来的 \(\operatorname{dfs}\) 序就会是对应的字典序的顺序了。

对于询问就比较简单了。

对于节点 \(u\)，这里对应的字符串数量有 \(\operatorname{cnt}_u\times (\operatorname{len}(u) - \operatorname{len}(\operatorname{fail}_u))\)。
然后按照 \(\operatorname{dfs}\) 序做前缀和 \(\operatorname{sum}_i\)。

那么对于询问 \(x\)。
找到最靠前的 \(i\) 使得 \(x\le \operatorname{sum}_i\)。
同时如果知道了 \(i\) 节点对应 SAM 的节点 \(p\)，就能知道字符串的长度为 \(\operatorname{len}(\operatorname{fail}_u) + 1 + \lfloor\frac{x - \operatorname{sum}_{i - 1} - 1}{\operatorname{cnt}_p}\rfloor\)，对于在哪个子串和右端点只需要初始建 Trie 时预处理，同时 \(\operatorname{fail}\) 树上 dfs 时对应处理好即可。

因为题目满足 \(x_j\) 递增，那么对应的 \(i\) 也是递增的，就不需要二分了。

时间复杂度 \(\mathcal{O}((\sum\limits_i|s_i|)|\Sigma|\log |\Sigma| + q)\)。

#include<bits/stdc++.h>
using ll = long long;
#define fi first
#define se second
const int maxn = 2e5 + 10;
int tr[maxn][26], m = 1;
std::pair<int, int> idw[maxn]; int siz[maxn];
std::string s[maxn];
int id[maxn], H[maxn], ed[maxn], cnt[maxn], len[maxn], ch[maxn][26], fail[maxn], tot = 1;
std::vector<int> son[maxn];
inline int append(int p, int c, int cnt_, int H_, int ed_) {
   int now = ++tot;
   len[now] = len[p] + 1, cnt[now] = cnt_, H[now] = H_, ed[now] = ed_;
   while (p && ! ch[p][c]) ch[p][c] = now, p = fail[p];
   if (! p) fail[now] = 1;
   else {
      int q = ch[p][c];
      if (len[p] + 1 == len[q]) fail[now] = q;
      else {
         int nq = ++tot;
         memcpy(ch[nq], ch[q], sizeof(ch[nq])), fail[nq] = fail[q], len[nq] = len[p] + 1;
         fail[q] = fail[now] = nq;
         while (p && ch[p][c] == q) ch[p][c] = nq, p = fail[p];
      }
   }
   return now;
}
void dfs1(int u) {
   for (int v : son[u])
      dfs1(v), cnt[u] += cnt[v], H[u] = H[v], ed[u] = ed[v];
}
ll sum[maxn]; int K, ids[maxn];
void dfs2(int u) {
   ids[++K] = u;
   sum[K] = sum[K - 1] + 1ll * cnt[u] * (len[u] - len[fail[u]]);
   for (int v : son[u])
      dfs2(v);
}
int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(0), std::cout.tie(0);
   int n; std::cin >> n;
   for (int i = 1; i <= n; i++) {
      std::cin >> s[i];
      std::reverse(s[i].begin(), s[i].end());
      for (int u = 1, j = 0; j < s[i].size(); j++) {
         int &v = tr[u][s[i][j] - 'a'];
         if (! v) v = ++m;
         u = v, idw[u] = {i, j}, siz[u]++;
      }
   }
   id[1] = 1;
   for (int i = 1; i <= m; i++)
      for (int c = 0; c < 26; c++)
         if (tr[i][c])
            id[tr[i][c]] = append(id[i], c, siz[tr[i][c]], idw[tr[i][c]].fi, idw[tr[i][c]].se);
   for (int i = 2; i <= tot; i++)
      son[fail[i]].push_back(i);
   dfs1(1);
   for (int i = 1; i <= tot; i++)
      std::sort(son[i].begin(), son[i].end(), [&](int x, int y) {
         return s[H[x]][ed[x] - len[i]] < s[H[y]][ed[y] - len[i]];
      });
   dfs2(1);
   int Q; std::cin >> Q;
   for (int w = 1; Q--; ) {
      ll x; std::cin >> x;
      while (sum[w] < x) w++;
      int p = ids[w], l = len[fail[p]] + 1 + (x - sum[w - 1] - 1) / cnt[p];
      std::cout << H[p] << ' ' << (s[H[p]].size() - ed[p]) << ' ' << (s[H[p]].size() - ed[p] + l - 1) << '\n';
   }
   return 0;
}