题目描述

给定一个由 $n$ 个字符 $0$ 和/或 $1$ 组成的字符串 $s$。

你需要制作 $m$ 份该字符串的副本，记第 $i$ 个副本为字符串 $t_i$。然后，你对每个副本恰好执行一次操作：对于第 $i$ 个副本，你将其子串 $[l_i, r_i]$（即从第 $l_i$ 个字符到第 $r_i$ 个字符，包含两端）进行排序。注意，每次操作只影响一个副本，每个副本也只被操作一次。

你的任务是计算 $t_1, t_2, \ldots, t_m$ 这 $m$ 个字符串中有多少个不同的字符串。注意，只有当至少有一个副本操作后与原始字符串 $s$ 完全相同时，才需要计入原始字符串 $s$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^5$），分别表示字符串 $s$ 的长度和副本的数量。

第二行包含 $n$ 个字符 $0$ 和/或 $1$，表示字符串 $s$。

接下来 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示对第 $i$ 个副本执行的操作。

所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。所有测试用例中 $m$ 的总和不超过 $2 \times 10^5$。

输出格式

输出一个整数，表示 $t_1, t_2, \ldots, t_m$ 这 $m$ 个字符串中不同字符串的数量。

说明/提示

以第一个样例为例。下方为按照输入操作顺序得到的副本，带下划线的为被排序的子串：

1. 101100 $\rightarrow$ 011100；
2. 101100 $\rightarrow$ 011100；
3. 101100 $\rightarrow$ 101100；
4. 101100 $\rightarrow$ 101100；
5. 101100 $\rightarrow$ 000111。

在 $t_1, t_2, t_3, t_4, t_5$ 中共有三种不同的字符串：000111、011100 和 101100。

再看第二个样例：

1. 100111 $\rightarrow$ 100111；
2. 100111 $\rightarrow$ 001111；
3. 100111 $\rightarrow$ 001111；
4. 100111 $\rightarrow$ 010111。

在 $t_1, t_2, t_3, t_4$ 中共有三种不同的字符串：001111、010111 和 100111。

由 ChatGPT 4.1 翻译

样例

3
6 5
101100
1 2
1 3
2 4
5 5
1 6
6 4
100111
2 2
1 4
1 3
1 2
1 1
0
1 1

3
3
1