Description：

给一个 $01$ 串，多次询问区间内最大 $LCS$ 。

$1\leqslant n\leqslant 10^5$

Solution：

考虑一个经典思路：扫描线，我们把所有询问按右端点排序，然后用数据结构维护所有左端点的答案，每当右面插入一个字符串的时候，我们可以计算一下他和左边所有串的 $LCS$ 然后和对应位置的值取 $\max$ ，那么最后的答案就是区间最大值。

考虑优化这个过程，我们把所有前缀反过来插到一棵 $trie$ 里，然后两个前缀的 $LCS$ 就是 $LCA$ 的深度，那么我们可以从这个点往上爬，同时更新其他子树里面的值为这个点的深度，这个还是可以优化的，如果我们有整个子树要更新，我们可以只更新最靠右的位置，这样在查询的时候还是能查到，那么我们可以对每个点记录一下子树中编号最大的点，然后从这个点往上爬的时候更新这些点，并且把这些点的最大值更新为当前数，对于整段的相同的值我们可以直接跳过，不难发现这个和 $LCT$ 的 $access$ 操作非常像，因此用 $LCT$ 维护复杂度就是对的了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 100010

int a[MAXN];

int getc()

{

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	return c - '0';

}

struct query

{

	int l,r,id;

}q[MAXN];

int ans[MAXN];

bool cmp_r(query a,query b){return a.r < b.r;}

namespace SAM

{

	struct node

	{

		int tr[26],par,maxl;

	}s[MAXN << 1];

	int ptr = 1,root = 1,last = 1;

	int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

	int pos[MAXN];

	void extend(int k,int id)

	{

		int p = last;

		int np = newnode(s[p].maxl + 1);

		pos[id] = np;

		for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

		if(p == 0)s[np].par = root;

		else

		{

			int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

			else

			{

				int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				s[q].par = s[np].par = nq;

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			}

		}

		last = np;

		return;

	}

}

namespace BIT

{

	int c[MAXN];

	int lowbit(int x){return x & (-x);}

	void add(int p,int x){for(int i = p;i >= 1;i -= lowbit(i))c[i] = max(c[i],x);return;}

	int query(int p){int res = 0;for(int i = p;i <= n;i += lowbit(i))res = max(c[i],res);return res;}

}

namespace LCT

{

	struct node

	{

		int c[2],fa;

		int col;

	}t[MAXN << 1];

	bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

	int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

	void pushdown(int rt){t[t[rt].c[0]].col = t[rt].col;t[t[rt].c[1]].col = t[rt].col;return;}

	void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

	void rotate(int x)

	{

		int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

		if(!isroot(y))t[z].c[fy] = x;

		t[x].fa = z;

		connect(t[x].c[fx ^ 1],y,fx);

		connect(y,x,fx ^ 1);

		return;

	}

	int stack[MAXN],top = 0;

	void splay(int x)

	{

		stack[++top] = x;

		for(int i = x;!isroot(i);i = t[i].fa)stack[++top] = t[i].fa;

		while(top)pushdown(stack[top--]);

		while(!isroot(x))

		{

			int y = t[x].fa;

			if(isroot(y)){rotate(x);break;}

			if(id(x) == id(y)){rotate(y);rotate(x);}

			else{rotate(x);rotate(x);}

		}

		return;

	}

	void access(int k,int p)

	{

		for(int i = 0;k;i = k,k = t[k].fa)

		{

			splay(k);

			BIT::add(t[k].col,SAM::s[k].maxl);

			t[k].c[1] = i;

			t[k].col = p;

		}

		return;

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)a[i] = getc();

	for(int i = 1;i <= n;++i)SAM::extend(a[i],i);

	for(int i = 2;i <= SAM::ptr;++i)LCT::t[i].fa = SAM::s[i].par;

	for(int i = 1;i <= m;++i)

	{

		q[i].l = rd();q[i].r = rd();

		q[i].id = i;

	}

	sort(q + 1,q + 1 + m,cmp_r);

	memset(BIT::c,0,sizeof(BIT::c));

	for(int r = 1,i = 1;r <= n;++r)

	{

		LCT::access(SAM::pos[r],r);

		while(q[i].r == r)

		{

			ans[q[i].id] = BIT::query(q[i].l);

			++i;

		}

	}

	for(int i = 1;i <= m;++i)printf("%d\n",ans[i]);

	return 0;

}