Problem C: 重复子串(string)

/*
一个性质？ right集合中只有相邻的位置才会有用
那么考虑set启发式合并， 能够求出大概nlogn个有用的对
那么将这些对按照右端点排序， 查询也按照右端点排序就可以离线维护信息
然后需要维护答案的话？？ 区间和一次函数取max？？？
应该有别的办法吧
普通线段树就好了 
*/

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
#include<iostream>
#define ll long long
#define mmp make_pair
#define M 200010
using namespace std;
int read() {
	int nm = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
	return nm * f;
}
set<int> st[M];
set<int>::iterator it, tt;
int ch[M][26], fa[M], len[M], sz[M], ans[M], lst = 1, cnt = 1, n, m, tp;
char s[M];
vector<int> to[M];
struct Note {
	int l, r, max;
	bool operator < (const Note &b) const {
		return this->r <	 b.r;
	}
} note[M * 60], que[M];

void insert(int pl, int c) {
	int p = ++cnt, f = lst;
	lst = p;
	len[p] = len[f] + 1;
	while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];
	if(f == 0) fa[p] = 1;
	else {
		int q = ch[f][c];
		if(len[q] == len[f] + 1) fa[p] = q;
		else {
			int nq = ++cnt;
			len[nq] = len[f] + 1;
			fa[nq] = fa[q];
			memcpy(ch[nq], ch[q], sizeof(ch[q]));
			fa[p] = fa[q] = nq;
			while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];
		}
	}
	sz[p] = 1;
	st[p].insert(pl);
}
int id[M];

bool cmp(int a, int b) {
	return sz[a] > sz[b];
}

void dfs(int now) {
	id[now] = now;
	int flag = sz[now];
	for(int i = 0; i < to[now].size(); i++) {
		int vj = to[now][i];
		dfs(vj);
		sz[now] += sz[vj];
	}
	if(now == 1) return;
	sort(to[now].begin(), to[now].end(), cmp);
	if(to[now].size() != 0) {
		id[now] = id[to[now][0]];
		if(flag) {
			int v = *st[now].begin();
			it = st[id[now]].lower_bound(v);
			if(it != st[id[now]].end()) {
				note[++tp] = (Note) {
					v, *it, len[now]
				};
			}
			if(it != st[id[now]].begin()) {
				it--;
				note[++tp] = (Note) {
					*it, v, len[now]
				};
			}
			st[id[now]].insert(v);
		}
		for(int i = 1; i < to[now].size(); i++) {
			int vj = to[now][i];
			it = st[id[vj]].begin();
			while(it != st[id[vj]].end()) {
				int v = *it++;
				tt = st[id[now]].lower_bound(v);
				if(tt != st[id[now]].end()) {
					note[++tp] = (Note) {
						v, *tt, len[now]
					};
				}
				if(tt != st[id[now]].begin()) {
					tt--;
					note[++tp] = (Note) {
						*tt, v, len[now]
					};
				}
				st[id[now]].insert(v);
			}
		}
	}
}


struct Black_ {
#define ls now << 1
#define rs now << 1 | 1
#define lson l, mid, now << 1
#define rson mid + 1, r, now << 1 | 1
	int t[M << 2], len[M << 2], ver[M << 2], maxx[M << 2];

	void build(int l, int r, int now) {
		len[now] = r - l + 1;
		ver[now] = -0x3e3e3e3e;
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(lson), build(rson);
	}

	void add(int now, int v) {
		ver[now] = max(ver[now], v);
		maxx[now] = max(maxx[now], ver[now] + len[now]);
	}
	void pushup(int now) {
		maxx[now] = max(maxx[now], max(maxx[ls], maxx[rs]));
	}
	void pushdown(int now) {
		add(rs, ver[now]);
		add(ls, ver[now] + len[rs]);
	}

	int que(int l, int r, int now, int ln, int rn) {
		if(l > rn || r < ln) return 0;
		if(l >= ln && r <= rn) return maxx[now];
		int mid = (l + r) >> 1;
		pushdown(now);
		return max(que(lson, ln, rn), que(rson, ln, rn));
	}
	void modi(int l, int r, int now, int ln, int rn, int v) {
		if(l > rn || r < ln) return;
		if(l >= ln && r <= rn) {
			add(now, v);
			return;
		}
		int mid = (l + r) >> 1;
		pushdown(now);
		modi(lson, ln, rn, v + min(max(rn - mid, 0), len[rs]));
		modi(rson, ln, rn, v);
		pushup(now);
	}
	void modify(int r, int v) {
		modi(1, n, 1, r - v + 1, r, 0);
	}
	int query(int l, int r) {
		return que(1, n, 1, l, r);
	}
} Seg;

int main() {
//	freopen("string_example_3.in", "r", stdin);	freopen("zz.out", "w", stdout);
	n = read(), m = read();
	scanf("%s", s + 1);
	for(int i = 1; i <= n; i++) insert(i, s[i] - 'a');
	for(int i = 2; i <= cnt; i++) to[fa[i]].push_back(i);
	dfs(1);
	for(int i = 1; i <= m; i++) que[i].l = read(), que[i].r = read(), que[i].max = i;
	sort(note + 1, note + tp + 1);
//	puts(s + 1);
//	for(int i = 1; i <= tp; i++) {
//		cerr<< note[i].l << " " << note[i].r << " " << note[i].max << "
";
//	}
//	cerr << tp << "
";
	sort(que + 1, que + m + 1);
	int tp1 = 1, tp2 = 1;
	Seg.build(1, n, 1);
	for(int i = 1; i <= n; i++) {
		while(tp1 <= tp && note[tp1].r <= i) {
			Seg.modify(note[tp1].l, note[tp1].max);
			tp1++;
		}
		while(tp2 <= m && que[tp2].r <= i) {
			ans[que[tp2].max] = Seg.query(que[tp2].l, que[tp2].r);
			tp2++;
		}
	}
	for(int i = 1; i <= m; i++) cout << ans[i] << "
";
	return 0;
}