upd: 修改了一些思路的表达，帮助理解。
首先膜拜 yyc 大佬出这样的毒瘤好题。另外感谢 永无岛、xtx1092515503、hs_black 提供的思路。这里整理了一下这些思路，可能会有所启发。
题意： 给定一个字符串构成的序列，多次查询给定区间内各字符串的最长公共子串长度。
提供一种 后缀数组 + 线段树合并 的在线单 \(\log\) 实现。
1. 思路
由于本题是区间查询版的 LCS2 所以笔者首先找到了在该题中使用的一种尺取做法。
下文中，极长表示不被任何满足条件的更大区间完全包含。具体来说，当询问 \([l,r]\) 的字符串的最长公共子串时，对于后缀数组上的一个区间，满足对任意 \([l,r]\) 中的字符串，该区间至少包含其一个后缀，则该区间包含的所有后缀的最长公共前缀，显然是这些字符串的一个极长公共子串。直接通过尺取法找到包含 \([l,r]\) 中所有字符串的每个极长区间，则对应公共子串长度即为所有取出的区间在高度数组上对应的区间 \(\min\)，对这些长度再取 \(\max\) 即为答案。很容易将一个后缀对应的原字符串编号联想成颜色，那么对于找到所有包含 \([l,r]\) 中每个颜色的串。
现在有多次询问，给定颜色区间，这种尺取法每次都需要 \(O(len)\) 时间，不能使用。考虑利用静态和离线的条件处理，可以发现，在需要尺取的这个序列（下称序列 \(a\)）中，任何两个区间对应的 \(\min\) 值（答案）都可以快速合并；并且两个区间对应含有的所有颜色也可以用启发式合并或线段树合并快速合并。
于是可以考虑按照高度从大到小的顺序，对 \(a\) 上的每个元素，合并它两边的比它高的元素所在的段。这样每次合并完之后，这个元素所在的段的最小值就是这个元素的高度，并且我们可以得到这个段包含的所有颜色区间 \([l,r]\)。这就可以用它的高度 \(h\) 更新那些被其中某个区间完全包含的询问区间的答案。显然，这里我们依次合并出的所有区间，其答案单调不增。
这样，询问是在线地找到第一次包含询问区间 \([l,r]\) 的颜色区间的对应答案。考虑把合并出的每个颜色区间 \([x,y]\) 用二元组 \((r,h)\) 表示其右端点及答案，存储在位置 \(x\) 上，则问题转变为查询 \([0,l]\) 中 \(y\ge r\) 的二元组中 \(h\) 的最大值。对该二元组按照 \(x\) 递增顺序，建立前缀值域主席树，在第 \(x\) 棵上的位置 \(y\) 插入数值 \(h\)，维护值域上区间最大值即可。
2. 优化
观察可以发现瓶颈在这里的启发式合并带两个 \(\log\)，但是很容易处理出一个段的所有颜色区间。而线段树合并似乎难以处理。但是 永无岛 大佬提出一种处理跨过线段树节点中点的区间的做法，可以胜任这种情况。然而这种做法有很多种具体实现，笔者使用的是个人认为比较清晰的做法。
具体来说，首先定义“跨越中点”段是指左儿子的后缀和右儿子的前缀拼成的段（这两者中也可能为空）。同时为了避免一个串被它的后代多次处理，只有这个段整体不是该节点前缀或后缀时才处理。显然任何极长颜色段就和线段树上的节点建立了一个双射。那么维护每个节点的前缀有颜色段和后缀有颜色段即可。
另一方面，如果一个节点在合并后它对应的区间长度没有变长，那么不用这个区间重复更新答案。
综上可以得到复杂度为 \(O((len + n + m)\log{n})\)，空间为 \(O((len + n)\log n + m)\)。这个空间是无法通过的，但如果离线实现，可以做到空间 \(O(n\log n + len + m)\)。
更新： 如果在线段树合并中，对于只有包含一个值的值域区间对应的线段树节点，打上标记而直到合并时再建出它的一个儿子，并重复利用被删除的节点空间，可以达到 \(O(n\log n + len + m)\) 的空间复杂度。
4. 实现
离线：
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
// Input
int n, m, len, x, y, ans[100005], str[420005], sa[420005], ht[420005];
int rt[420005], a[100005], b[420005], fa[420005], now;
pair<int, int> baf[420005];
char c;
vector<pair<short, int>> u[20010];
// Sa
namespace Sa {
int n, m, rk[420005], x[420005], y[420005];
void init() {
m = 20002;
for (int i = 1; i <= n; ++i) ++fa[x[i] = str[i]];
for (int i = 2; i <= m; ++i) fa[i] += fa[i - 1];
for (int i = n; i >= 1; --i) sa[fa[x[i]]--] = i;
for (int k = 1; k <= n; k <<= 1) {
int num = 0;
for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
for (int i = 1; i <= n; ++i)
if (sa[i] > k) y[++num] = sa[i] - k;
for (int i = 1; i <= m; ++i) fa[i] = 0;
for (int i = 1; i <= n; ++i) ++fa[x[i]];
for (int i = 2; i <= m; ++i) fa[i] += fa[i - 1];
for (int i = n; i >= 1; --i) sa[fa[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1;
num = 1;
for (int i = 2; i <= n; ++i)
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if (num >= n) break;
m = num;
}
int k = 0;
for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
for (int i = 1; i <= n; ++i) {
if (rk[i] == 1) continue;
if (k) --k;
int j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && str[i + k] == str[j + k]) ++k;
ht[rk[i]] = k;
}
}
}
namespace Ans {
int tot;
struct Node {
int l, r, x;
} t[400010];
inline int build(int l, int r) {
int p = ++tot;
if (l == r)
sort(u[l].rbegin(), u[l].rend()), t[p].x = (u[l].empty() ? 0x3f3f3f3f : u[l].back().first);
else {
int mid = (l + r) >> 1;
t[p].l = build(l, mid);
t[p].r = build(mid + 1, r);
t[p].x = min(t[t[p].l].x, t[t[p].r].x);
}
return p;
}
inline void query(int p, int l, int r, int x, int y) {
if (r < x || t[p].x > y) return;
int mid = (l + r) >> 1;
if (l == r) {
while (!u[l].empty() && u[l].back().first <= y) ans[u[l].back().second] = now, u[l].pop_back();
t[p].x = (u[l].empty() ? 0x3f3f3f3f : u[l].back().first);
} else {
query(t[p].l, l, mid, x, y), query(t[p].r, mid + 1, r, x, y);
t[p].x = min(t[t[p].l].x, t[t[p].r].x);
}
}
}
// Segment Tree
namespace Seg {
struct Node {
int l, r;
short lv, rv;
} t[8000001];
int tot;
inline void pushup(int p, int l, int r) {
int mid = (l + r) >> 1;
if (t[p].l) t[p].lv = t[t[p].l].lv;
if (t[p].r) t[p].rv = t[t[p].r].rv;
if (t[t[p].l].lv == mid - l + 1) t[p].lv += t[t[p].r].lv;
if (t[t[p].r].rv == r - mid) t[p].rv += t[t[p].l].rv;
}
inline int insert(int l, int r, int i) {
int p = ++tot;
if (l == r) t[p].lv = t[p].rv = 1;
else {
int mid = (l + r) >> 1;
if (i <= mid) t[p].l = insert(l, mid, i), t[p].lv = t[t[p].l].lv;
else t[p].r = insert(mid + 1, r, i), t[p].rv = t[t[p].r].rv;
}
return p;
}
inline int merge(int p, int q, int l, int r, int k = 0) {
if (p == q) return p;
if (!p || !q) return p ^ q;
int mid = (l + r) >> 1, lt = t[t[p].l].rv, rt = t[t[p].r].lv;
t[p].lv = max(t[p].lv, t[q].lv), t[p].rv = max(t[p].rv, t[q].rv);
t[p].l = merge(t[p].l, t[q].l, l, mid, 1), t[p].r = merge(t[p].r, t[q].r, mid + 1, r, 2);
pushup(p, l, r);
if (t[t[p].l].rv == lt && t[t[p].r].lv == rt) return p;
if ((t[t[p].l].rv || t[t[p].r].lv) &&
(!k || (k == 2 && t[t[p].l].rv < mid - l + 1) || (k == 1 && t[t[p].r].lv < r - mid)))
Ans::query(1, 1, n, mid - t[t[p].l].rv + 1, mid + t[t[p].r].lv);
return p;
}
};
inline int read() {
char c = getchar();
int x = 0, f = 1;
while (!isdigit(c)) f = (c == '-' ? -1 : f), c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
inline int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int i, j, num;
signed main() {
n = read(), m = read();
for (i = 1; i <= n; ++i) {
while (!isdigit(c)) c = getchar();
while (isdigit(c)) str[++len] = c - '0' + 1, b[len] = i, c = getchar();
str[++len] = i + 2;
}
Sa::n = len, Sa::init();
for (i = 1; i <= len; ++i){
if(b[sa[i]]) baf[++num] = make_pair(-ht[i], i), fa[i] = i, rt[i] = Seg::insert(1, n, b[sa[i]]);
else fa[i] = i - 1;
} sort(baf + 2, baf + 1 + num);
for (int i = 1; i <= m; ++i) a[i] = read(), u[a[i]].emplace_back(read(), i);
Ans::build(1, n);
for (i = 2; i <= num; ++i) {
x = baf[i].second, now = -baf[i].first;
rt[find(x)] = Seg::merge(rt[find(x)], rt[find(x - 1)], 1, n), fa[find(x - 1)] = find(x);
}
for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}
以下代码为了可读性和在线，效率较低（此题线段树合并可能只有理论上才优于启发式合并），不开 O2 不保证随时都可以通过。
在线：
#include <algorithm>
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
// Input
int n, m, len, x, y, sa[500005], ht[500005];
pair<int, int> baf[500005];
int rt[500005], b[500005], fa[500005], now;
char c;
short str[500005];
vector<pair<short, short>> u[20010];
// Sa
namespace Sa {
int n, m, ans, rk[500005], c[500005], x[500005], y[500005];
void init() {
m = 20002;
for (int i = 1; i <= n; ++i) ++c[x[i] = str[i]];
for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
for (int k = 1; k <= n; k <<= 1) {
int num = 0;
for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
for (int i = 1; i <= n; ++i)
if (sa[i] > k) y[++num] = sa[i] - k;
for (int i = 1; i <= m; ++i) c[i] = 0;
for (int i = 1; i <= n; ++i) ++c[x[i]];
for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1;
num = 1;
for (int i = 2; i <= n; ++i)
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if (num >= n) break;
m = num;
}
int k = 0;
for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
for (int i = 1; i <= n; ++i) {
if (rk[i] == 1) continue;
if (k) --k;
int j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && str[i + k] == str[j + k]) ++k;
ht[rk[i]] = k;
}
// for (int i = 1; i <= n; ++i) cout << sa[i] << " ";
// cout << endl;
// for (int i = 1; i <= n; ++i) cout << ht[i] << " ";
// cout << endl;
}
}
namespace Ans {
int tot, rt[20010];
struct Node {
int l, r, x;
} t[200010];
inline int insert(int p, int l, int r, int i, int x) {
int tp = ++tot;
t[tp] = t[p], t[tp].x = max(t[tp].x, x);
if (l ^ r) {
int mid = (l + r) >> 1;
if (i <= mid)
t[tp].l = insert(t[p].l, l, mid, i, x);
else
t[tp].r = insert(t[p].r, mid + 1, r, i, x);
}
return tp;
}
inline int ask(int p, int pl, int pr, int l) {
if (pl >= l) return t[p].x;
int mid = (pl + pr) >> 1, ans = 0;
if (l <= mid) ans = max(ans, ask(t[p].l, pl, mid, l));
return max(ans, ask(t[p].r, mid + 1, pr, l));
}
}
// Segment Tree
namespace Seg {
struct Node {
int l, r;
short lv, rv, lt, rt;
} t[8000001];
int tot, bk[8000001], top;
inline void pushup(int p, int l, int r) {
int mid = (l + r) >> 1;
if (t[p].l) t[p].lv = t[t[p].l].lv;
if (t[p].r) t[p].rv = t[t[p].r].rv;
if (t[t[p].l].lv == mid - l + 1) t[p].lv += t[t[p].r].lv;
if (t[t[p].r].rv == r - mid) t[p].rv += t[t[p].l].rv;
}
inline int insert(int l, int r, int i) {
int p = ++tot;
if (l == r)
t[p].lv = t[p].rv = 1;
else {
int mid = (l + r) >> 1;
if (i <= mid)
t[p].l = insert(l, mid, i), t[p].lv = t[t[p].l].lv;
else
t[p].r = insert(mid + 1, r, i), t[p].rv = t[t[p].r].rv;
}
return p;
}
inline int merge(int p, int q, int l, int r, int k = 0) {
if (p == q) return p;
if (!p || !q) return p ^ q;
int mid = (l + r) >> 1, lt = t[t[p].l].rv, rt = t[t[p].r].lv;
t[p].lv = max(t[p].lv, t[q].lv), t[p].rv = max(t[p].rv, t[q].rv);
t[p].l = merge(t[p].l, t[q].l, l, mid, 1), t[p].r = merge(t[p].r, t[q].r, mid + 1, r, 2);
pushup(p, l, r);
t[q] = {}, bk[++top] = q;
if (t[t[p].l].rv == lt && t[t[p].r].lv == rt) return p;
if ((t[t[p].l].rv || t[t[p].r].lv) &&
(!k || (k == 2 && t[t[p].l].rv < mid - l + 1) || (k == 1 && t[t[p].r].lv < r - mid)))
u[mid - t[t[p].l].rv + 1].emplace_back(mid + t[t[p].r].lv, now);
return p;
}
};
inline int read() {
char c = getchar();
int x = 0, f = 1;
while (!isdigit(c)) f = (c == '-' ? -1 : f), c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
inline int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int i, j, num;
signed main() {
n = read(), m = read();
for (i = 1; i <= n; ++i) {
while (!isdigit(c)) c = getchar();
while (isdigit(c)) str[++len] = c - '0' + 1, b[len] = i, c = getchar();
str[++len] = i + 2;
}
Sa::n = len, Sa::init();
for (i = 1; i <= len; ++i){
if(b[sa[i]]) baf[++num] = make_pair(-ht[i], i), fa[i] = i, rt[i] = Seg::insert(1, n, b[sa[i]]);
else fa[i] = i - 1;
} sort(baf + 2, baf + 1 + num);
for (i = 2; i <= num; ++i) {
x = baf[i].second, now = -baf[i].first;
// j = b[sa[x - 1]] ? x - 1 : x - 2;
rt[find(x)] = Seg::merge(rt[find(x)], rt[find(x - 1)], 1, n), fa[find(x - 1)] = find(x);
}
for (i = 1; i <= n; ++i) {
Ans::rt[i] = Ans::rt[i - 1];
for (j = 0; j < u[i].size(); j++)
Ans::rt[i] = Ans::insert(Ans::rt[i], 1, n, u[i][j].first, u[i][j].second);
}
while (m--) {
x = read(), y = read();
printf("%d\n", Ans::ask(Ans::rt[x], 1, n, y));
}
return 0;
}