B4181 [厦门小学生 C++ 2024] 有趣子序列

本试题为 2024 年厦门市小学生 C++ 语言**复赛**试题，数据为洛谷自造。 **初赛**为笔试。

小唐最近在研究一个长为 $n$ 的 $01$ 字符串 $S$（下标从 $1$ 开始）。 他很喜欢其子区间和子序列，例如：如下表的 $01$ 字符串 $S = \tt{01011010}$。 | $S_1$ | $S_2$ | $S_3$ | $S_4$ | $S_5$ | $S_6$ | $S_7$ | $S_8$ | |:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:| | $0$ | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $0$ | - 子区间 $[2,4]$ 即为：$S_2, S_3, S_4$ 这样一个在原 $S$ 串中连续的一段序列； - 子序列即类如：$S_2, S_4, S_6, S_7$ 这样一个按原 $S$ 串顺序的，可连续、可不连续的序列。 所以，子区间肯定是子序列，但子序列不一定是子区间。 小唐会询问你 $Q$ 次，每次询问给出一个 $S$ 的子区间 $[l,r]$，他想知道是否存在 $S$ 的一个“有趣子序列”，其满足： 1. “有趣子序列”和询问的子区间 $[l,r]$ 相同； 例：如果询问的子区间是 $[2,4]$，其中，子序列 $S_2, S_6, S_7$ 和询问的子区间 $S_2, S_3, S_4$ 中的字符按顺序一一对应相同; 2. “有趣子序列”不是从 $S$ 中选出的一段子区间。 例：子序列 $S_2, S_6, S_7$ 并不是原 $S$ 串中连续的一段序列，即不是原 $S$ 串的一段子区间。 请对于每次询问 $[l,r]$，输出 $\tt{Yes}$ 或 $\tt{No}$，分别表示存在或不存在这样的 “有趣子序列”。

**本题有多组数据。** - 第一行一个非负整数 $T$，表示数据组数。 - 接下来 $T$ 组数据，对于每组数据： - 第一行两个非负整数 $n$ 和 $q$，表示字符串长度和询问数。 - 第二行一个 $01$ 字符串 $s$。 - 接下来 $q$ 行，每行两个正整数 $l,r$，表示询问的子区间。

对于每组数据： - 对于每个询问，输出一行 $\tt{Yes}$ 或 $\tt{No}$ 表示答案。

### 样例解释 1 - 对于第一组数据，可以选择的子序列下标依次为：不存在，$(1,2,4)$，$(3,4,6)$。 - 对于第二组数据，可以选择的子序列下标依次为：不存在，$(1,3)$。 ### 数据范围 对于所有数据，满足 $1 \leq n \leq 1 \times 10^5$，$1 \leq q \leq 1 \times 10^5$，$1 \leq l\ {\color{red}\leq}\ r \leq n$。 | 数据点编号 | $T\leq$ | $n\leq$ | $q\leq$ | 特殊性质 | |:------------:|:----:|:----:|:----:|:----------:| | $1$ | $100$ | $4$ | $1$ | | | $2$ | $100$ | $10$ | $10$ | | | $3$ | $10$ | $12$ | $100$ | | | $4$ | $10$ | $100$ | $100$ | | | $5, 6$ | $10$ | $1000$ | $1000$ | | | $7$ | $5$ | $1 \times 10^5$| $1 \times 10^5$| $l=1$ | | $8, 9, 10$ | $5$ | $1 \times 10^5$| $1 \times 10^5$| | 特殊性质：$l=1$ 表示子区间左边界为 $1$。