CF1849C Binary String Copying

给定一个由 $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 翻译