题解 | #简单字符串#

题意

给定一个字符串 ，每次询问，任意分成段。问每一段的最大字典序最小是什么。

题解

初学Lyndon,根据 。第一想法就是找到那个 然后后面的都比它大。

但是询问的左边界不一定在Lyndon边界上，我们找到，即后面第一个比大的后缀，位置为。那么这个区间就是一个待选区间。如果足够大，答案就是。

考虑不够大的情况，注意到。(其中 代表串重复出现边)。我们只需要通过找到这个重复了多少次。然后尽量均分即可。注意细节，参考代码注释。

#include <bits/stdc++.h>
#define ll long long
#define enl putchar('\n')
#define all(x) (x).begin(),(x).end()
#define debug(x) printf(" "#x":%d\n",x);
using namespace std;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
typedef pair<int, int> pii;
char buf[1 << 21], * p1 = buf, * p2 = buf, obuf[1 << 21], * o = obuf, of[35];
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1)res = res * a % mod; n >>= 1; a = a * a % mod; }return res; }
template <class T = int>inline T read() { T s = 0, f = 1; char c = gc(); for (; !isdigit(c); c = gc())if (c == '-')f = -1; for (; isdigit(c); c = gc())s = s * 10 + c - '0'; return s * f; }
inline void read(int* a, int n) { for (int i = 1; i <= n; ++i)a[i] = read(); }
inline int inal(char* s) { int n = 0; for (s[0] = gc(); !isalpha(s[0]); s[0] = gc()); for (; isalpha(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline void outd(int* a, int n) { for (int i = 1; i <= n; ++i)printf("%d ", a[i]); enl; }
int n, m, q;
struct Sa {     //俩字符串连一起记得开俩倍空间
    char s[MAXN];
    int SA[MAXN], rk[MAXN], oldrk[MAXN << 1], id[MAXN], key1[MAXN], cnt[MAXN];  //SA排名为i对应原字符串下标，rk下标为i的后缀排名
    int height[MAXN], n;    //height与上一个排名相同的个数，height[1]=0
    inline bool cmp(int x, int y, int w) {
        return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
    }
    inline void getSA() {
        memset(cnt, 0, sizeof(cnt));
        memset(rk, 0, sizeof(rk));
        n = strlen(s + 1);
        int m = 127;
        for (int i = 1; i <= n; ++i)++cnt[rk[i] = s[i]];
        for (int i = 1; i <= m; ++i)cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; --i)SA[cnt[rk[i]]--] = i;
        for (int len = 1, p;; len <<= 1, m = p) {
            p = 0;
            for (int i = n; i > n - len; --i)id[++p] = i;
            for (int i = 1; i <= n; ++i)
                if (SA[i] > len)id[++p] = SA[i] - len;
            memset(cnt, 0, sizeof(cnt));
            for (int i = 1; i <= n; ++i)++cnt[key1[i] = rk[id[i]]];
            for (int i = 1; i <= m; ++i)cnt[i] += cnt[i - 1];
            for (int i = n; i >= 1; --i)SA[cnt[key1[i]]--] = id[i];
            memcpy(oldrk + 1, rk + 1, n * sizeof(int));
            p = 0;
            for (int i = 1; i <= n; ++i)
                rk[SA[i]] = cmp(SA[i], SA[i - 1], len) ? p : ++p;
            if (p == n)break;
        }
        // for (int i = 1; i <= n; ++i)printf("%d ", SA[i]); printf("\n");
        // for (int i = 1; i <= n; ++i)printf("%d ", rk[i]); printf("\n");
    }
    inline void getHeight() {
        for (int i = 1, k = 0; i <= n; ++i) {
            if (rk[i] == 0)continue;
            if (k)--k;
            while (s[i + k] == s[SA[rk[i] - 1] + k])++k;
            height[rk[i]] = k;
        }
    }
    int st[MAXN][20], lg[MAXN];
    inline void initST() {
        lg[1] = 0;
        for (int i = 2; i <= n; i++)lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i <= n; i++)st[i][0] = height[i];
        for (int j = 1; j <= lg[n]; j++)
            for (int i = 1; i <= n - (1 << j) + 1; i++)
                st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
    inline int RQM(int x, int y) {
        int t = lg[y - x + 1];
        return min(st[x][t], st[y - (1 << t) + 1][t]);
    }
    inline int LCP(int x, int y) {
        x = rk[x], y = rk[y];
        if (x > y)swap(x, y);
        return RQM(x + 1, y);
    }
};

int lim[MAXN];
struct Duval :Sa {
    vector<int>gap;
    void duval(char* s, int n) {
        for (int i = 1, j, k; i <= n;) {
            for (j = i, k = i + 1; k <= n && s[k] >= s[j]; ++k)
                if (s[k] > s[j])j = i;
                else ++j;
            while (i <= j) {
                i += k - j;
                gap.push_back(i - 1);
            }
        }
    }
    bool compare(int x, int y) {
        int len = LCP(x, y);
        return s[x + len] < s[y + len];
    }
    int ly[MAXN];
    void getsuf(bool op = 0) {   // 0 大 1 小
        ly[n] = n + 1; lim[n] = 0;
        for (int i = n - 1; i >= 1; --i) {
            ly[i] = i + 1;
            while (ly[i] != n + 1 && compare(ly[i], i) == op)
                ly[i] = ly[ly[i]];
            lim[i] = lim[ly[i]] + 1;
        }
    }
}p;


char s[MAXN];
void solve() {
    n = inal(s + 1);
    p.duval(s, n);
    memcpy(p.s, s, sizeof(s));
    p.getSA();
    p.getHeight();
    p.initST();
    p.getsuf();
    q = read();
    // outd(lim, n);
    while (q--) {
        int l = read(), k = read(), r = p.ly[l];
        if (k == 1)printf("%d %d\n", l, n);
        else if (k > lim[l])printf("%d %d\n", l, r - 1);
        else {
            // 一定是某段重复出现的最大，后面的都是更小的
            int lcp = p.LCP(l, r), t = l + lcp - 1;
            int re = lcp / (r - l) + 1;
            if (re % k == 0) {
                //均分，每段都一样，最后一段可能加上后面的更小的
                if (l + re * (r - l) == n + 1) {
                    printf("%d %d\n", l, l + re / k * (r - l) - 1);
                } else {
                    printf("%d %d\n", l + (re - re / k) * (r - l), n);
                }
            } else {
                //尽量均分
                printf("%d %d\n", l, l + (re / k + 1) * (r - l) - 1);
            }
        }
    }
}
signed main(signed argc, char const* argv[]) {
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //=============================================================
    int TxT = 1;
    // TxT = read();
    while (TxT--)
        solve();
    //=============================================================
#ifdef LOCAL
    end :
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}