P7361 「JZOI-1」拜神 题解

namespace lowspeed_song {

inline void init() {
}

char s[N];

int root[N];
int lc[M], rc[M], tot;
u16 mi[M];

namespace Suffix_Array {
    int sa[N], rk[N], buc[N], height[N], n, idx;
    struct Node {
        int x[2], buc;
        inline Node() { x[0] = x[1] = buc = 0; }
        inline Node(int a, int b, int c) { x[0] = b, x[1] = a, buc = c; }
    } a[N], b[N];
    inline void sort(int up) {
        for (int i : {0, 1}) {
            memset(buc, 0, sizeof buc);
            for (int j = 1; j <= n; ++j) ++buc[a[j].x[i]];
            for (int j = 1; j <= up; ++j) buc[j] += buc[j - 1];
            for (int j = n; j; --j) b[buc[a[j].x[i]]--] = a[j];
            for (int j = 1; j <= n; ++j) a[j] = b[j];
        }
        int idx = 1;
        rk[a[1].buc] = 1;
        for (int i = 2; i <= n; ++i)
            if (a[i].x[0] == a[i - 1].x[0] && a[i].x[1] == a[i - 1].x[1]) rk[a[i].buc] = idx;
            else rk[a[i].buc] = ++idx;
    }
    inline void build() {
        for (int i = 1; i <= n; ++i) a[i] = Node(s[i], 1, i);
        sort(128);
        for (int i = 1; i < n; i <<= 1) {
            for (int j = 1; j <= n; ++j) a[j] = Node(rk[j], (i + j <= n) ? rk[i + j] : 0, j);
            sort(n);
        } for (int i = 1; i <= n; ++i) sa[rk[i]] = i;
        for (int i = 1; i <= n; ++i)
            if (rk[i] == 1) height[rk[i]] = 0;
            else {
                int p = sa[rk[i] - 1], l = max<int>(0, height[rk[i - 1]] - 1);
                while (s[i + l] == s[p + l]) ++l;
                height[rk[i]] = l;
            }
    }
} using namespace Suffix_Array;

vector<int> e[N];

inline int mdf(int rt, int l, int r, int pos, int val) {
    int nw = ++tot;
    lc[nw] = lc[rt], rc[nw] = rc[rt], mi[nw] = mi[rt];
    if (l == r) return mi[nw] = val, nw;
    int mid = l + r >> 1;
    if (pos <= mid) lc[nw] = mdf(lc[rt], l, mid, pos, val);
    else rc[nw] = mdf(rc[rt], mid + 1, r, pos, val);
    mi[nw] = min(mi[lc[nw]], mi[rc[nw]]);
    return nw;
}

inline int qry(int rt, int l, int r, int ll, int rr) {
    if (!rt) return inf;
    if (ll <= l && r <= rr) return mi[rt];
    int mid = l + r >> 1, res = inf;
    if (ll <= mid) res = qry(lc[rt], l, mid, ll, rr);
    if (mid < rr) res = min(res, qry(rc[rt], mid + 1, r, ll, rr));
    return res;
}

int fa[N];
set<int> se[N];
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int tag_idx, tag[N], cp[N];
inline void chg(int pos, int v) {
    if (!tag[pos]) cp[++tag_idx] = pos;
    tag[pos] = v;
}
inline void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (se[x].size() < se[y].size()) swap(x, y);
    fa[y] = x;
    for (const int &p : se[y]) {
        auto it = se[x].lower_bound(p);
        if (it != se[x].end()) chg(p, *it);
        if (it != se[x].begin()) chg(*prev(it), p);
        se[x].emplace(p);
    } se[y].clear();
}

inline void sol() {
    int q; cin >> n >> q;
    scanf("%s", s + 1);
    build();
    mi[0] = 64000;
    for (int i = 2; i <= n; ++i)
        if (height[i]) e[height[i]].emplace_back(i);
    for (int i = 1; i <= n; ++i) fa[i] = i, se[i].emplace(i);
    for (int len = n - 1; len; --len) {
        tag_idx = 0;
        for (int &i : e[len]) merge(sa[i - 1], sa[i]);
        root[len] = root[len + 1];
        for (int i = 1; i <= tag_idx; ++i) {
            root[len] = mdf(root[len], 1, n, cp[i], tag[cp[i]]);
            tag[cp[i]] = 0;
        }
    }
    while (q--) {
        int l, r; cin >> l >> r;
        int L = 1, R = r - l + 1, best = 0;
        while (L <= R) {
            int mid = L + R >> 1;
            if (qry(root[mid], 1, n, l, r - mid + 1) <= r - mid + 1) best = mid, L = mid + 1;
            else R = mid - 1;
        } cout << best << '\n';
    }
}

} // namespace lowspeed_song