A9007. Ilya and Queries
编程题
普及/提高-
知识点
题目描述
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.
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)$ .
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