301640: CF313B. Ilya and Queries
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Ilya and Queries
题意翻译
llya的朋友要参加IT考试,可他有一些不会的题目,你要帮帮他! 他得到了一个长度为n的字符串(s=s1s2s3s4...sn,其中只包含.和#),还有m个问题,每个问题包含两个数a,b。 你的任务是找出每个问题的答案,每个问题的答案各包含一个整数p,代表字符串由a位到b位有几位满足s i=si+1 ### 输入格式 长度为n的字符串(2<=n<=10^5),m个问题(1<=n<=10^5),接下来m行每行两个整数a,b(1<=a<b<=n)。 ### 输出格式 m行,每行一个整数p。 ## 注意 字符串首位被记为第一位而非第零位!题目描述
Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam. You've got string $ s=s_{1}s_{2}...\ s_{n} $ ( $ n $ is the length of the string), consisting only of characters "." and "\#" and $ m $ queries. Each query is described by a pair of integers $ l_{i},r_{i} $ $ (1<=l_{i}<r_{i}<=n) $ . The answer to the query $ l_{i},r_{i} $ is the number of such integers $ i $ $ (l_{i}<=i<r_{i}) $ , that $ s_{i}=s_{i+1} $ . Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.输入输出格式
输入格式
The first line contains string $ s $ of length $ n $ $ (2<=n<=10^{5}) $ . It is guaranteed that the given string only consists of characters "." and "\#". The next line contains integer $ m $ $ (1<=m<=10^{5}) $ — the number of queries. Each of the next $ m $ lines contains the description of the corresponding query. The $ i $ -th line contains integers $ l_{i},r_{i} $ $ (1<=l_{i}<r_{i}<=n) $ .
输出格式
Print $ m $ integers — the answers to the queries in the order in which they are given in the input.
输入输出样例
输入样例 #1
......
4
3 4
2 3
1 6
2 6
输出样例 #1
1
1
5
4
输入样例 #2
#..###
5
1 3
5 6
1 5
3 6
3 4
输出样例 #2
1
1
2
2
0