← 返回题目列表

Codeforces · 1849/C

C. 二进制字符串复制

中文机器翻译题面 查看原题

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

你制作该字符串的 $$$m$$$ 个副本,令第 $$$i$$$ 个副本为字符串 $$$t_i$$$。然后,您对每个副本执行一次操作:对于第 $$$i$$$ 个副本,对其子字符串 $$$[l_i; 进行排序; r_i]$$$(从第 $$$l_i$$$ 个字符到第 $$$r_i$$$ 个字符的子字符串,包括两个端点)。请注意,每个操作仅影响一个副本,每个副本仅受一个操作影响。

你的任务是计算 $$$t_1, t_2, \ldots, t_m$$$ 中不同字符串的数量。请注意,只有在操作后至少有一个副本保持不变的情况下,才应计算初始字符串 $$$s$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是 $$$s$$$ 的长度和副本数。

第二行包含 $$$n$$$ 字符 0 和/或 1 — 字符串 $$$s$$$。

然后是 $$$m$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 应用于第 $$$i$$$ 副本的操作的描述。

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

输出

打印一个整数 — $$$t_1, t_2, \ldots, t_m$$$ 中不同字符串的数量。

示例

输入 #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

输出 #1

3
3
1

注意

考虑第一个例子。以下副本按输入操作的顺序给出。带下划线的子字符串是已排序的子字符串:

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。