题意

有一个长度为 $n$ 的字符串 $s$，定义 $s[l,r]$ 表示区间 $[l,r]$ 所组成的子串。有 $m$ 次询问，每次给定 $a,b,c,d$，查询 $s[a,b]$ 所有子串 $s[l,r]$ 中，$\max\{lcp(s[l,r],s[c,d])\}$ 的值。

$1 \le n,m \le 10^5$。

分析

首先，$r$ 一定是取 $b$ 的，因为这样子可以最小化长度带来的影响，肯定不亏。

但是这个 $lcp$ 受到长度限制，而不同位置收到的限制还不一样。这就会导致我们直接找 $height$ 最大值的方法没用了。

input:
12 1
abcabcabcdef
1 5 4 12
output:
5

如果直接找最大值，会输出 $2$。

要避免长度对答案带来的影响，我们可以考虑二分，因为答案有很明显的单调性。考虑二分到 $x$，那么子串就是 $s[i,i+x-1]$，这里就要 $i \ge a,i+x-1 \le b$，所以 $i \in [a,b-x+1]$。于是我们要求的就是是否存在 $i \in [a,b-x+1],lcp(s[i,n],s[c,n]) \ge x$。我们不好对 $lcp$ 求 $max$，因为 $lcp$ 本质是 $min$。但是我们可以反过来考虑，对于所有 $lcp(s[i,n],s[c,n]) \ge x$ 的 $i$，是否 $\exists i \in [a,b-x+1]$。因为 $lcp$ 本质上就是 $height$ 的 $min$，这个 $i$ 的 $rk$ 一定是一段区间。这个区间可以直接二分 $+$ ST 表做到单次 $O(\log n)$。然后我们就只要查询对应的区间内是否有 $sa_i \in [a,b-x+1]$，可以直接主席树（可持久化线段树）做，时间复杂度也是 $O(\log n)$。最终时间复杂度是 $O(n\log^2n)$。

刚好 $100$ 行。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define N 200005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, sa[N], oldsa[N], rk[N], oldrk[N], t[N], height[N], a, b, c, d;
char s[N];
il void SA(){
    int M = 127;
    memset (t, 0, sizeof t);
    for (int i = 1; i <= n; i++) t[rk[i] = s[i]]++;
    for (int i = 1; i <= M; i++) t[i] += t[i - 1];
    for (int i = n; i >= 1; i--) sa[t[rk[i]]--] = i;
    for (int w = 1; w < n; w <<= 1, M = n){
        memcpy(oldsa, sa, sizeof oldsa), memset (t, 0, sizeof t);
        for (int i = 1; i <= n; i++) t[rk[oldsa[i] + w]]++;
        for (int i = 1; i <= M; i++) t[i] += t[i - 1];
        for (int i = n; i >= 1; i--) sa[t[rk[oldsa[i] + w]]--] = oldsa[i];
        memcpy(oldsa, sa, sizeof oldsa), memset (t, 0, sizeof t);
        for (int i = 1; i <= n; i++) t[rk[oldsa[i]]]++;
        for (int i = 1; i <= M; i++) t[i] += t[i - 1];
        for (int i = n; i >= 1; i--) sa[t[rk[oldsa[i]]]--] = oldsa[i];
        memcpy(oldrk, rk, sizeof oldrk);
        for (int p = 0, i = 1; i <= n; i++)
            if (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) rk[sa[i]] = p;
            else rk[sa[i]] = ++p;
    }
}
il void HT(){
    for (int i = 1, k = 0; i <= n; i++) if (rk[i] >= 1){
        if (k) k--;
        while (i + k <= n && sa[rk[i] - 1] + k <= n && s[i + k] == s[sa[rk[i] - 1] + k]) k++;
        height[rk[i]] = k;
    }
}
int rt[N], tr[N << 6], ls[N << 6], rs[N << 6], ep;// Segment Tree
void add(int &p, int t, int l, int r, int x){
    p = ++ep, tr[p] = tr[t] + 1, ls[p] = ls[t], rs[p] = rs[t];
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (x <= mid) add(ls[p], ls[t], l, mid, x), rs[p] = rs[t];
    else add(rs[p], rs[t], mid + 1, r, x), ls[p] = ls[t];
}
int query(int a, int b, int l, int r, int nl, int nr){
    if (nl <= l && r <= nr) return tr[b] - tr[a];
    int mid = (l + r) >> 1, ans = 0;
    if (nl <= mid) ans += query(ls[a], ls[b], l, mid, nl, nr);
    if (nr > mid) ans += query(rs[a], rs[b], mid + 1, r, nl, nr);
    return ans;
}
struct ST_table{//ST table
    int f[N][35], lg[N];
    il void init(){
        for (int i = 1; i <= n; i++) f[i][0] = height[i];
        for (int j = 1; j <= 30; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    }
    il int mink(int l, int r){
        int p = lg[r - l + 1];
        return min(f[l][p], f[r - (1 << p) + 1][p]);
    }
}ST;
il bool check(int x){
    int xl, xr, l = 1, r = rk[c] - 1, ans = rk[c];
    while (l <= r){
        int mid = (l + r) >> 1;
        if (ST.mink(mid + 1, rk[c]) >= x) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    xl = ans, l = rk[c] + 1, r = n, ans = rk[c];
    while (l <= r){
        int mid = (l + r) >> 1;
        if (ST.mink(rk[c] + 1, mid) >= x) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    xr = ans;
    if (query(rt[xl - 1], rt[xr], 1, n, a, b - x + 1)) return 1;
    return 0;
}
int main(){
    n = rd(), m = rd(), scanf ("%s", s + 1), SA(), HT(), ST.init();
    for (int i = 1; i <= n; i++) add(rt[i], rt[i - 1], 1, n, sa[i]);rt[n + 1] = rt[n];
    while (m--){
        a = rd(), b = rd(), c = rd(), d = rd();
        int l = 0, r = min(b - a + 1, d - c + 1), ans = -1;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (check(mid)) l = mid + 1, ans = mid;
            else r = mid - 1;
        }
        printf ("%d\n", ans);
    }
    return 0;
}