简要题意

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

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

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

数据范围

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

主要思路

这个题看上去挺板子的，而且题目也提示了是后缀自动机。但是我自己写下来，其实细节还是很多的。这道题算是对后缀自动机 link 树的一个灵活运用了。

首先，我们来大概构想一下这个排序长什么样。显然，它一定是若干段相同长度的字符串首尾相接而成的，而且每一段字符串内部遵守字典序排序。暴力的想法便是将所有的子串处理出来，然后进行回答。

那么这如何与后缀自动机结合呢？我们知道这些子串的数量级很大，但是后缀自动机仍能良好的表示这些子串，原因是它可以将子串进行压缩。

我们知道后缀自动机的 link 树：每个 endpos 集合作为父亲通过树边连接它的子集，所以一个集合的子节点所代表的 endpos 集合的后缀的交集便是该集合所代表的最长后缀，这个长度被记录在节点的 dep 之中。然而，儿子和父亲所代表的最长后缀的差并不完全为一，这就是后缀自动机压缩子串的方式。

我们可以将字符串反转，并构建后缀自动机，这样所有的后缀便是前缀了。那么我们如何才能定位排名为 \(k\) 的字符串所在的 endpos 集合呢？

我们可以考虑一个不那么优越的处理方法：我们可以来尝试列出这些子串的排序，但是是以一种压缩后的方式。我们先将当前长度定为 \(clen = 0\)，然后将 link 树上第二层的节点加入「候选集合」之中（\(pset\)）。这时候，我们将候选集合中后缀最短的长度赋给 \(clen\)，说明当前候选集合完全包含了所有长度至少为 \(clen\) 的后缀（候选集合中可能会有比这个长的后缀，但是绝对没有比这个短的）。此时，我们将候选集合按字典序排序（其实是取所有后缀后 \(clen\) 的结果，但是显然直接按字典序排序并不会影响结果）。此时集合大小为 \(|pset|\)，那么我们可以检查 \(k\) 是否在 \([1, clen \times |pset|]\) 之中。

其实这时我们已经用压缩的方式表示出了完整排序中的 \(clen\) 段了。回顾一下，此时这些段中的第一段就是候选集合中按字典序排序之后所有后缀长度为 \(1\) 的子后缀。那么，第二段便是候选集合中按字典序排序之后所有后缀长度为 \(2\) 的子后缀。

直到 \(clen\) 时，候选集合中出现了至少一个后缀，不能表示长度超过 \(clen\) 的后缀。此时我们要将其从集合中剔除，并加入该后缀的子 endpos 集合。

当 \(clen\) 判断完了之后，我们进入下一轮。此时的 \(clen\) 则需要更新为现有「候选集合」中最短的后缀长度，并将原有的 \(clen\) 赋值给 \(plen\)。此时，我们检查 \(k\) 是否在 \( [part_1 + 1, part_1 + (clen – plen) \times |pset|] \) 之中，其中 \(part_1\) 便是上一轮中子串的数量。为什么是 \(clen – plen\)？因为这段长度便是被后缀自动机压缩的长度，我们现在将其展开即可。

之后一直这样处理，总会处理到 \(k\) 命中区间的时刻。命中时，我们使用取模运算找到包含排名为 \(k\) 的字符串的后缀在循环节中的位置，并且使用除法算出循环的次数，也就可以得出该字符串的具体长度。维护 SAM 的时候维护一下最早出现的位置，然后加一下答案就出来了。

这就是处理一次的方式。什么？你要处理 \(Q\) 次？其实很显然，离线之后便可以顺序地算出答案。至于如何维护「候选集合」，也就是说，如何快速查找字典序第 \(k\) 小的后缀，并且还要知道哪些后缀的深度最小。

笔者在此处使用了两个简单的数据结构维护之。首先，在 link 树上进行 dfs 便可以处理出一个父亲下子节点的相对字典序，在进行一次 dfs 记录 dfs 序便是字典序了。查找第 \(k\) 小的后缀的编号事实上可以使用树状数组维护；同时，欲维护深度最小的后缀，只需要使用优先队列即可。

接下来请看代码。

代码

// J.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

int n, Q, tree[MAX_N << 1], anti[MAX_N << 1];
char str[MAX_N];
pli queries[MAX_N];
pii ansBox[MAX_N];

struct node
{
    int dep, link, ch[26], pos, lc, dfn;
} nodes[MAX_N << 1];

int ptot = 1, last_ptr = 1, bucket[MAX_N << 1], rnk[MAX_N << 1];
vector<int> G[MAX_N << 1];

void insert(int c, int idx)
{
    int pre = last_ptr, p = last_ptr = ++ptot;
    nodes[p].dep = nodes[pre].dep + 1, nodes[p].pos = idx;
    while (pre && nodes[pre].ch[c] == 0)
        nodes[pre].ch[c] = p, pre = nodes[pre].link;
    if (pre == 0)
        nodes[p].link = 1;
    else
    {
        int q = nodes[pre].ch[c];
        if (nodes[q].dep == nodes[pre].dep + 1)
            nodes[p].link = q;
        else
        {
            int clone = ++ptot;
            nodes[clone] = nodes[q], nodes[clone].dep = nodes[pre].dep + 1;
            nodes[p].link = nodes[q].link = clone;
            while (pre && nodes[pre].ch[c] == q)
                nodes[pre].ch[c] = clone, pre = nodes[pre].link;
        }
    }
}

void radixSort()
{
    for (int i = 1; i <= ptot; i++)
        bucket[nodes[i].dep]++;
    for (int i = 1; i <= ptot; i++)
        bucket[i] += bucket[i - 1];
    for (int i = 1; i <= ptot; i++)
        rnk[bucket[nodes[i].dep]--] = i;
    for (int i = 2; i <= ptot; i++)
        G[nodes[rnk[i]].link].push_back(rnk[i]);
}

int cnt;

void dfs1(int u)
{
    for (int v : G[u])
    {
        dfs1(v);
        nodes[u].pos = min(nodes[u].pos, nodes[v].pos);
        nodes[v].lc = str[nodes[v].pos + nodes[u].dep] - 'a';
    }
    sort(G[u].begin(), G[u].end(), [](const int &lhs, const int &rhs)
         { return nodes[lhs].lc < nodes[rhs].lc; });
}

void dfs2(int u)
{
    cnt++, nodes[u].dfn = cnt, anti[cnt] = u;
    for (int v : G[u])
        dfs2(v);
}

inline int lowbit(int x) { return x & -x; }

void update(int x, int d)
{
    for (; x <= ptot; x += lowbit(x))
        tree[x] += d;
}

int kth(int k)
{
    int ret = 0;
    for (int i = 22; i >= 0; i--)
    {
        ret += (1 << i);
        if (ret >= ptot || k <= tree[ret])
            ret -= (1 << i);
        else
            k -= tree[ret];
    }
    return ret + 1;
}

int main()
{
    scanf("%s", str + 1), n = strlen(str + 1), scanf("%d", &Q);
    for (int i = n; i >= 1; i--)
        insert(str[i] - 'a', i);
    for (int i = 1; i <= Q; i++)
        scanf("%lld", &queries[i].first), queries[i].second = i;
    sort(queries + 1, queries + 1 + Q), radixSort(), dfs1(1), dfs2(1);
    int qptr = 1, clen = 0, plen = 0;
    ll acc = 0;
    priority_queue<pii> pq;
    for (int v : G[1])
        pq.push(make_pair(-nodes[v].dep, v)), update(nodes[v].dfn, 1);
    while (!pq.empty())
    {
        clen = -pq.top().first;
        int cycle_len = clen - plen, cycle_width = pq.size();
        ll amount = 1LL * cycle_len * cycle_width;
        while (qptr <= Q && queries[qptr].first > acc && queries[qptr].first <= acc + amount)
        {
            ll order = queries[qptr].first - acc;
            ll nxt = (order - 1) % cycle_width, slen = (order - 1) / cycle_width;
            int id = anti[kth(nxt + 1)];
            ansBox[queries[qptr].second] = make_pair(nodes[id].pos, nodes[id].pos + clen + slen - 1);
            qptr++;
        }
        while (!pq.empty() && pq.top().first == -clen)
        {
            int u = pq.top().second;
            pq.pop();
            update(nodes[u].dfn, -1);
            for (int v : G[u])
                pq.push(make_pair(-nodes[v].dep, v)), update(nodes[v].dfn, 1);
        }
        plen = clen, acc += amount;
    }
    for (int i = 1; i <= Q; i++)
        if (ansBox[i].first == 0 && ansBox[i].second == 0)
            puts("-1 -1");
        else
            printf("%d %d\n", ansBox[i].first, ansBox[i].second);
    return 0;
}