#P9042. [2017年备战省选]a

    ID: 9248 传统题 4000ms 888MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600提高+/省选-后缀数组Kasai 算法Kruskal 重构树小并大合并集合有序集合有限候选集缩减离线查询查询排序树状数组

[2017年备战省选]a

题目描述

给定一个长度为 nn 的 01 串。每个位置 ii 对应以 ii 结尾、从串首开始的一个前缀。两个不同前缀的相似度是它们的最长公共后缀长度。

对于每次给出的区间 [l,r][l,r],在结束位置均落在区间内的前缀中,求两个不同前缀所能达到的最大相似度。

输入格式

第一行两个整数 n,mn,m,表示串长和询问数。第二行一个长度为 nn 的 01 串。

接下来 mm 行,每行两个正整数 l,rl,r,满足 1≤l<r≤n1\le l<r\le n。

输出格式

每次询问输出一行一个整数,表示最大相似度。

样例 1

4 2
0101
1 3
2 4
1
2

原题的第二组样例见原比赛样例数据文件夹。

数据范围

测试点 nn mm
1–2 100
3–4 300 1000
5–6 5000
7–10 100000 300
11–14 50000
15–20 100000

原 PDF 题面