首先建 SAM，然后问题转化为在 Parent Tree 上编号在 \([l,r]\) 内的点对的 LCA 的深度的最大值。
考虑一个贪心，先在树上做一次启发式合并，维护子树内代表前缀的结点，然后启发式合并时把每个点的前驱后继找出来，与该点形成数对产生贡献。
然后就变成了一个二维数点问题了。
容易发现点对数量规模和启发式合并的复杂度是相同的。
但是我是来写 LCT 的（
考虑从左到右枚举右端点然后维护对应左端点的答案，那么右端点增加一时，要检查其对应结点到根的链上的点维护的最晚出现位置和当前右端点的贡献，然后把它们的最晚出现位置改成当前右端点。
同时在 BIT 上维护后缀最大值即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
using namespace std;
const int N = 1e5;
int n,m,ed[N + 5];
char s[N + 5];
vector< pair<int,int> > qry[N + 5];
int ans[N + 5];
namespace SAM
{
struct node
{
int ch[2];
int fa,len;
} sam[(N << 1) + 5];
int las = 1,tot = 1;
inline void insert(int x)
{
int p = ++tot,cur = las;
sam[p].len = sam[cur].len + 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
int nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
las = p;
}
}
namespace BIT
{
int c[N + 5];
inline void update(int x,int k)
{
for(;x;x -= lowbit(x))
c[x] = max(c[x],k);
}
inline int query(int x)
{
int ret = 0;
for(;x <= n;x += lowbit(x))
ret = max(ret,c[x]);
return ret;
}
}
namespace LCT
{
struct node
{
int fa;
int las,tag;
int ch[2];
} tr[(N << 1) + 5];
inline void down(int p)
{
if(tr[p].tag)
tr[tr[p].ch[0]].las = tr[tr[p].ch[0]].tag = tr[p].tag,
tr[tr[p].ch[1]].las = tr[tr[p].ch[1]].tag = tr[p].tag,
tr[p].tag = 0;
}
inline void rotate(int p)
{
int x = tr[p].fa,y = tr[x].fa,d = chk(p),t = tr[p].ch[d ^ 1];
is_son(x) && (tr[y].ch[chk(x)] = p,1),
tr[p].ch[d ^ 1] = x,tr[x].ch[d] = t,
t && (tr[t].fa = x),
tr[x].fa = p,tr[p].fa = y;
}
inline void splay(int p)
{
static int s[N + 5];
int top = 0;
s[++top] = p;
for(register int x = p;is_son(x);s[++top] = x = tr[x].fa);
for(;top;down(s[top--]));
for(register int x;is_son(p);rotate(p))
x = tr[p].fa,
is_son(x) && (rotate((chk(p) ^ chk(x)) ? p : x),1);
}
inline void access(int p,int pos)
{
for(register int cur = p,x = 0;cur;cur = tr[x = cur].fa)
splay(cur),tr[cur].ch[1] = x,
tr[cur].las && (BIT::update(tr[cur].las,SAM::sam[cur].len),1);
splay(p),tr[p].las = tr[p].tag = pos;
}
inline void init()
{
for(register int i = 1;i <= SAM::tot;++i)
tr[i].fa = SAM::sam[i].fa;
}
}
int main()
{
scanf("%d%d%s",&n,&m,s + 1);
for(register int i = 1;i <= n;++i)
SAM::insert(s[i] - '0'),ed[i] = SAM::las;
LCT::init();
int l,r;
for(register int i = 1;i <= m;++i)
scanf("%d%d",&l,&r),qry[r].push_back(make_pair(l,i));
for(register int i = 1;i <= n;++i)
{
LCT::access(ed[i],i);
for(register vector< pair<int,int> >::iterator it = qry[i].begin();it != qry[i].end();++it)
ans[it->second] = BIT::query(it->first);
}
for(register int i = 1;i <= m;++i)
printf("%d\n",ans[i]);
}