//其实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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *