第 3 题搭塔 (`tornjevi`)

本题使用文件输入输出：输入文件 tornjevi.in，输出文件 tornjevi.out。

本题满分 110。

题目描述

有 $n$ 块正方体积木，每块积木的颜色是红色、蓝色二者之一。第 $i$ 块积木的边长为 $i$ 。

定义一座塔是合法的，当且仅当：

$q$ 次独立询问，每次询问给定 $l, r$ ，求出：如果用边长 $l, \ldots, r$ 的积木搭塔，至少要搭几座塔。

第一行，两个正整数 $n, q$ （ $1 \le n, q \le 10^5$ ）。

第二行，一个长度为 $n$ 的字符串 $s$ 。 $s_i = \mathrm{C}$ ，表示边长为 $i$ 的积木为红色；否则 $s_i = \mathrm{P}$ ，表示边长为 $i$ 的积木为蓝色。

接下来 $q$ 行，每行两个正整数 $l_i, r_i$ （ $1 \le l_i \le r_i \le n$ ），描述一次询问。

输出 $q$ 行，第 $i$ 行一个正整数，描述第 $i$ 个询问的答案。

输入：

7 4
PPCPPCC
1 7
1 5
3 7
4 5

输出：

输入：

6 2
CCCCCC
1 6
2 5

输出：

6
4

输入：

16 1
PPPCPCCCCCCPPPPP
1 16

输出：

样例二解释：所有积木都是红色的，所以只能搭出仅包含一块积木的塔。显然对于一次询问 $l, r$ 的答案为 $r - l + 1$ 。