rt，调了一整天了，愣是没看出来一个问题，除了hack数据外全WA，求大佬帮看看，一定关注！谢谢！

ps：二分写的是左闭右闭的版本（也可以理解为左开右开？）

#include <algorithm>
#include <cstring>
#include <iostream>
#define lc(x) tr[x].left_son
#define rc(x) tr[x].right_son

using namespace std;

const int N = 2e5 + 5;

int n, m, sa[N], rk[N], ork[N], h[N], lg[N], st[N][18];
char s[N];
int root[N], idx; // 主席树
struct
{
    int l, r, left_son, right_son, sum;
} tr[20 * N];

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(lc(u) = ++idx, l, mid), build(rc(u) = ++idx, mid + 1, r);
}

void modify(int prv, int u, int p)
{
    tr[u] = tr[prv], tr[u].sum++;
    if (tr[u].l == tr[u].r)
        return;
    int mid = tr[u].l + tr[u].r >> 1;
    if (p <= mid)
        modify(lc(prv), lc(u) = ++idx, p);
    else
        modify(rc(prv), rc(u) = ++idx, p);
}

int query(int prv, int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum - tr[prv].sum;
    int mid = tr[u].l + tr[u].r >> 1, sum = 0;
    if (l <= mid)
        sum = query(lc(prv), lc(u), l, r);
    if (r > mid)
        sum += query(rc(prv), rc(u), l, r);
    return sum;
}

void sfx_ary()
{
    for (int i = 1; i <= n; i++)
        sa[i] = i, rk[i] = s[i];
    for (int w = 1, r = 0; r < n; w <<= 1) // nlog^2n SA
    {
        sort(sa + 1, sa + n + 1, [w](int x, int y) { return rk[x] != rk[y] ? rk[x] < rk[y] : rk[x + w] < rk[y + w]; });
        memcpy(ork, rk, sizeof rk), r = 0;
        for (int i = 1; i <= n; i++)
        {
            if (ork[sa[i]] != ork[sa[i - 1]] || ork[sa[i] + w] != ork[sa[i - 1] + w])
                r++;
            rk[sa[i]] = r;
        }
    }
    for (int i = 1, k = 0; i <= n; i++) // 求 height
    {
        if (rk[i] == 1)
            continue;
        if (k)
            k--;
        while (s[i + k] == s[sa[rk[i] - 1] + k])
            k++;
        h[rk[i]] = k;
    }
    lg[0] = -1;
    for (int i = 1; i <= n; i++) // rmq
        st[i][0] = h[i], lg[i] = lg[i >> 1] + 1;
    for (int i = 1; 1 << i <= n; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[j][i] = min(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
    root[0] = ++idx, build(root[0], 1, n);
    for (int i = 1; i <= n; i++)
        root[i] = ++idx, modify(root[i - 1], root[i], sa[i]);
}

int gmin(int l, int r)
{
    int len = lg[r - l + 1];
    return min(st[l][len], st[r - (1 << len) + 1][len]);
}

bool check(int sl, int sr, int pos, int val)
{
    int lp, rp, l = 0, r = sa[pos];
    while (l + 1 < r)
    {
        int mid = l + r >> 1;
        (gmin(mid + 1, sa[pos]) >= val ? r : l) = mid;
    }
    lp = r, l = sa[pos], r = n + 1;
    while (l + 1 < r)
    {
        int mid = l + r >> 1;
        (gmin(sa[pos] + 1, mid) >= val ? l : r) = mid;
    }
    rp = l;
    return query(root[lp - 1], root[rp], sl, sr);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> s + 1;
    sfx_ary();
    while (m--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int l = 0, r = min(b - a, d - c) + 2;
        while (l + 1 < r)
        {
            int mid = l + r >> 1;
            (check(a, b - mid + 1, c, mid) ? l : r) = mid;
        }
        cout << l << "\n";
    }
    return 0;
}