2. 醉酒
【题目描述】
小X家住在一条东西向的大街上。在他们家的东面,自东向西依次分布着n幢相似的房屋,编号为1到n,可以用一个长度为n的字符串表示这n幢房屋的颜色。
小X的父亲经常喝醉酒,每次醉酒后他都会稀里糊涂地走到第Ai幢房屋前,然后坚信他现在第Bi幢房屋前。虽然他喝醉了,但是他依然能分清每幢房屋的颜色,并且掏出地图进行比较,只有房屋颜色和地图上一致时,他才会继续向西走。当他发现自己的错误或者不能前进时,就会停下来。现在,小X记录下了每次的数据Ai和Bi,他希望知道父亲最多走过多少幢相同颜色的房屋。
【输入格式】
第一行两个数n和m,表示n幢房屋和m次询问。
第二行一个长度为n的字符串,仅包含大写字母。
接下来m行,每行两个数Ai和Bi。
【输出格式】
m行,每个一个数,表示小X的父亲父亲最多走过多少幢相同颜色的房屋。
Sample 1
Input
10 6
AABBCCAABB
1 7
7 1
3 4
4 9
2 5
5 5
Output
4
4
1
1
0
6
Limitation
1s, 128MiB for each test case.
【数据范围】
对于60%的数据,n,m≤100。
对于80%的数据,n≤1000。
对于100%的数据,n,m≤100000,Ai,Bi≤n。
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 2
- 已通过
- 2
- 通过率
- 100%
- 上传者