//其实 XZY 本来做的是要求询问一次复杂度 $log _ 2N$的然而 XZY 太菜了只能找了个数据范围更小的题来做了。。。

1. 题目

传送门=￣ω￣=

2. 题解

emmmm…

就是询问排名第 $k$大子串

用后缀自动机做一发

得到后缀自动机的 DAG 以后 DP 得到从某个点出发能得到多少个不同子串（因为从某点出发随便走都可以得到原串的一个子串）

然后对于询问第 $k$个子串，先由字典序从小到大枚举后继节点，如果后继节点可以得到的子串个数小于 $k$，则让 $k$减去可以得到的子串个数，否则进入该后继继续查找第 $k$个子串

丢完代码就跑真刺激

#include <bits/stdc++.h>

#define NS (200005)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct SAM
{
    struct N
    {
        int nxt[26], pre, mxl;
        int& operator [] (const int a) {return nxt[a];}
    } e[NS];
    int sz, lst; LL f[NS];
    SAM() {sz = lst = 1;}
    void insert(int c)
    {
        int a = ++sz, p = lst;
        lst = a, e[a].mxl = e[p].mxl + 1;
        while (p && !e[p][c]) e[p][c] = a, p = e[p].pre;
        if (!p) {e[a].pre = 1; return;}
        int q = e[p][c];
        if (e[q].mxl == e[p].mxl + 1) {e[a].pre = q; return;}
        int nq = ++sz;
        e[nq] = e[q], e[nq].mxl = e[p].mxl + 1;
        e[a].pre = e[q].pre = nq;
        while (e[p][c] == q) e[p][c] = nq, p = e[p].pre;
    }
    void szdfs(int a)
    {
        if (f[a]) return;
        f[a] = 1;
        for (int i = 0; i < 26; i += 1)
            if (e[a][i]) szdfs(e[a][i]), f[a] += f[e[a][i]];
    }
    void query(int a, LL k)
    {
        if (!k) {putchar(10); return;}
        int nxt = -1;
        for (int i = 0; i < 26; i += 1)
            if (e[a][i])
            {
                if (f[e[a][i]] < k) k -= f[e[a][i]];
                else {putchar(i + 'a'), k--, nxt = e[a][i]; break;}
            }
        query(nxt, k);
    }
} sam;

char str[NS];

int n, q;

int main(int argc, char const* argv[])
{
    scanf("%s", str), n = strlen(str);
    for (int i = 0; i < n; i += 1) sam.insert(str[i] - 'a');
    sam.szdfs(1), IN(q); LL a;
    while (q--) IN(a), sam.query(1, a);
    return 0;
}