AT_s8pc_5_h Percepts of Atcoder题解

· · 题解

AT_s8pc_5_h Percepts of Atcoder

题目大意

给定一个字符串 S，将它的所有子串去重后按字典序从小到大排序，每次询问第 K 个子串的最后 p 位。

题目分析

与子串相关，可以先建出 S 的序列自动机，再顺便记一下从每一位到最后的子串数量，这样就能统计出总共的子串数（因为 K\le 10^{18}，所以数量可以与 10^{18} 取 min ，这样就不用担心爆 long long ，后面默认都进行取 min 操作）。

先考虑暴力，每次从起始点开始跳，依次从 a 到 z，将 K 减去以这个字母为后继（下一个字符）的子串数，直到找到第一个子串数大于当前 K 的字母，再从这个字母往下跳，时间复杂度为 O\left(Q|S|\right)。

暴力复杂度的瓶颈在于最劣情况需要跳 |S| 次，考虑进行优化。可以参考重链剖分，对序列自动机进行类似 DAG 链剖分的操作，可以以子串数量最多的后继字母作为重儿子（如果有 10^{18}，则选择第一个，因为后面的无实际作用），与重链剖分类似，每跳一次轻儿子子串数量至少减半，之后再在每条重链上进行倍增，找到在这条重链上能跳的最远距离，记录一下操作顺序，再倒序取后缀即可，由于 \sum p\le 3\times 10^{7}，所以这并不是复杂度瓶颈。

时间复杂度为 O(Q \log K \log |S|)（严谨来说，应为 O\left(Q \log {\min\left(sum_{\text{子串总数}},10^{18}\right)} \log |S|+\sum p\right)）。

代码

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
const ll N = 3e5 + 10, inf = 1e18, L = 20;
int n, q, nxt[N][26], skp[L][N];
ll k, p, cnt[N], l[L][N], r[L][N], sum[L][N];
string s;
ll read()
{
    ll f = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        f = 10 * f + ch - '0', ch = getchar();
    return f;
}
void read(string& s)
{
    s = '0';
    char ch = getchar();
    while (!(ch >= 'a' && ch <= 'z'))
        ch = getchar();
    while (ch >= 'a' && ch <= 'z')
        s += ch, ch = getchar();
}
void write(string s)
{
    for (auto i : s) {
        putchar(i);
    }
    putchar('\n');
}
void init()
{
    read(s);
    q = read();
    n = s.size() - 1;
    for (auto& i : nxt[n])
        i = n + 1;
    cnt[n] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < 26; j++) {
            nxt[i][j] = nxt[i + 1][j];
        }
        nxt[i][s[i + 1] - 'a'] = i + 1;
        if (i > 0)
            cnt[i] = 1;
        ll mmax = -inf;
        for (auto j : nxt[i]) {
            if (mmax < cnt[j]) {
                skp[0][i] = j;
                sum[0][i] = cnt[i];
                l[0][i] = cnt[i] + 1;
                r[0][i] = min(cnt[i] + cnt[j], inf);
                mmax = cnt[j];
            }
            cnt[i] = min(cnt[i] + cnt[j], inf);
        }
    }
    l[0][n + 1] = 1;
    r[0][n + 1] = 0;
    skp[0][n + 1] = n + 1;
    for (int i = 1; i < L; i++) {
        for (int j = 0; j <= n + 1; j++) {
            int u = skp[i - 1][j];
            skp[i][j] = skp[i - 1][u];
            sum[i][j] = min(sum[i - 1][j] + sum[i - 1][u], inf);
            l[i][j] = max(sum[i - 1][j] + l[i - 1][u], l[i - 1][j]);
            r[i][j] = min(sum[i - 1][j] + r[i - 1][u], r[i - 1][j]);
        }
    }
}
inline string query()
{
    if (k > cnt[0]) {
        return "-1";
    }
    vector<pair<bool, pair<int, int>>> pos;
    int nw = 0;
    while (k) {
        for (int i = L - 1; i >= 0; i--) {
            if (k >= l[i][nw] && k <= r[i][nw]) {
                pos.push_back({ 1, { nw, i } });
                k -= sum[i][nw];
                nw = skp[i][nw];
            }
        }
        if (nw)
            k--;
        if (!k)
            break;
        for (int i = 0; i < 26; i++) {
            if (cnt[nxt[nw][i]] >= k) {
                pos.push_back({ 0, { nw, i } });
                nw = nxt[nw][i];
                break;
            }
            k -= cnt[nxt[nw][i]];
        }
    }
    string ans = "";
    for (int i = pos.size() - 1; i >= 0; i--) {
        if (!pos[i].fir) {
            ans += char(pos[i].sec.sec + 'a');
        } else {
            nw = pos[i].sec.fir;
            string temp = "";
            for (int j = 0; j < (1 << pos[i].sec.sec); j++) {
                nw = skp[0][nw];
                if (nw == n + 1)
                    break;
                temp += s[nw];
            }
            reverse(temp.begin(), temp.end());
            ans += temp;
        }
        if ((int)ans.size() >= p) {
            ans.resize(p);
            reverse(ans.begin(), ans.end());
            return ans;
        }
    }
    reverse(ans.begin(), ans.end());
    return ans;
}
int main()
{
    init();
    for (int i = 1; i <= q; i++) {
        k = read();
        p = read();
        write(query());
    }
    return 0;
}