trie树

$\qquad$因为01串是随机的，所以lcp的长度不会太长，据说有个公式，蒟蒻表示不会，所以我们猜测lcp长度都不超过40，这样我们就将每一个后缀的前40个位置插入到trie树中即可。

$\qquad$从左到右将后缀的前40位插入字典树，字典树路径上存下最后一次访问该点的是以哪一个位置开始后缀，第二次访问这个深度为dep节点的时候就表示当前后缀与之前的一个后缀的$lcp\ge dep$，维护一下这40个值就可以了，查询的时候，直接访问这40个值。

代码

#include <bits/stdc++.h>
#define R register
#define eps 1e-12
#define INF (1<<30)
#define LL long long
#define LINF (1ll<<60)
#define MM(x, y) memset(x, y, sizeof x)
#define Fo(i, x, y) for(R int i=x; i<=y; ++i)
#define Ro(i, x, y) for(R int i=x; i>=y; --i)
using namespace std;
template<typename T> inline T Max(R T x, R T y) {return x > y ? x : y;}
template<typename T> inline T Min(R T x, R T y) {return x < y ? x : y;}
template<typename T> inline void in(R T &x)
{
	static int ch; static bool flag;
	for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
	for(x=0; ch>='0'&&ch<='9'; ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
	x = flag ? -x : x;
}
/*************************************Samle*************************************/
#define N 100005
int cnt, n, Q, fina[50*N], o[50*N], son[50*N][2]; LL ans[N]; char ch[N];
struct QUE{int l, r, id;}q[N];
bool operator < (R QUE a, R QUE b) {return a.r < b.r || (a.r == b.r && a.l < b.l);}
inline void insert(R int x)
{
	R int p = 0;
	for(int i=0; x+i<=n&&i+1<=40; ++i)
	{
		R int w = ch[x+i] - '0';
		if(!son[p][w])
		{
			son[p][w] = ++cnt;
			fina[cnt] = x;
		}
		else
		{
			o[i+1] = Max(o[i+1], fina[son[p][w]]);
			fina[son[p][w]] = x;
		}
		p = son[p][w];
	}
}
int main()
{
	in(n), in(Q); scanf("%s", ch+1);
	Fo(i, 1, Q) in(q[i].l), in(q[i].r), q[i].id = i;
	sort(q+1, q+Q+1); R int T = 1;
	Fo(i, 1, n)
	{
		insert(i);
		while(T <= Q && q[T].r == i)
		{
			for(R int i=1; i<=40; ++i)
			{
				if(o[i] >= q[T].l)
					ans[q[T].id] += 1ll * i * (o[i]-Max(q[T].l-1, o[i+1]));
				else 
					break;
			}
			++T;
		}
	}
	Fo(i, 1, Q) printf("%lld\n", ans[i]);
	return 0;
}