P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi

本题满分 $110$。

有 $n$ 块正方体积木，每块积木的颜色是 $\colorbox{#e82548}{\textcolor{white}{\textsf{红}}}\colorbox{87b3ed}{\textcolor{white}{\textsf{蓝}}}$ 二者之一。第 $i$ 块积木的边长为 $i$。 定义一座塔是合法的，当且仅当： - 相邻的两个积木块的颜色不同； - 从下到上，积木块的边长严格递减。 $q$ 次独立询问，每次询问给定 $l,r$，求出：如果用边长 $l,\ldots,r$ 的积木搭塔，至少要搭几座塔。

第一行，两个正整数 $n,q$（$1\le n,q\le 10^5$）。 第二行，一个长度为 $n$ 的字符串 $s$。$s_i=\texttt{C}$，表示边长为 $i$ 的积木为 $\colorbox{#e82548}{\textcolor{white}{\textsf{红}}}$ 色；否则 $s_i=\texttt{P}$，表示边长为 $i$ 的积木为 $\colorbox{87b3ed}{\textcolor{white}{\textsf{蓝}}}$ 色。 接下来 $q$ 行，每行两个正整数 $l_i,r_i$（$1\le l_i\le r_i\le n$），描述一次询问。

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

### 样例解释 **样例二解释**：所有积木都是 $\colorbox{#e82548}{\textcolor{white}{\textsf{红}}}$ 色的，所以只能搭出仅包含一块积木的塔。显然对于一次询问 $l,r$ 的答案为 $r-l+1$。 ### 子任务 - $\text{Subtask 1 (23 pts)}$：$n,q\le 10$； - $\text{Subtask 2 (38 pts)}$：$n,q\le 1000$； - $\text{Subtask 3 (25 pts)}$：至多有 $20$ 块 $\colorbox{87b3ed}{\textcolor{white}{\textsf{蓝}}}$ 色积木。 - $\text{Subtask 4 (24 pts)}$：无额外限制。