← 返回题目列表

Codeforces · 1978/E

E. 计算机

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

Sasha有两个二进制字符串$$$s$$$和$$$t$$$,长度相同$$$n$$$,由字符0和1组成。

还有一种计算机可以对相同长度$$$k$$$的二进制串$$$a$$$和$$$b$$$进行两种操作:

1. 如果 $$$a_{i} = a_{i + 2} =$$$ 0,则可以分配 $$$b_{i + 1} :=$$$ 1 ($$$1 \le i \le k - 2$$$)。
2. 如果 $$$b_{i} = b_{i + 2} =$$$ 1,则可以分配 $$$a_{i + 1} :=$$$ 1 ($$$1 \le i \le k - 2$$$)。

Sasha 对以下问题感兴趣:如果我们考虑字符串 $$$a=s_ls_{l+1}\ldots s_r$$$ 和字符串 $$$b=t_lt_{l+1}\ldots t_r$$$,那么使用计算机可以获取字符串 $$$a$$$ 中 1 个字符的最大数量是多少。由于 Sasha 很好奇但很懒,因此由您来回答他感兴趣的几对 $$$(l_i, r_i)$$$ 的问题。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 和 $$$t$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$,由字符0和1组成。

每个测试用例的第三行包含一个长度为$$$n$$$的二进制字符串$$$t$$$,由字符0和1组成。

每个测试用例的第四行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。

以下行中的第 $$$i$$$ 包含两个整数 $$$l_{i}$$$ 和 $$$r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le n$$$) — Sasha 感兴趣的第 $$$i$$$ 对子字符串的边界。

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

输出

对于每个测试用例,输出 $$$q$$$ 整数 - 所有查询的答案。

示例

输入 #1

3
4
1111
0000
2
1 2
2 4
4
1010
1101
2
1 3
1 4
6
010101
011010
5
2 3
1 6
2 5
4 4
3 6

输出 #1

2
3
2
3
1
4
3
1
2

注意

在第一个测试用例中:

- 在第一个查询中,$$$a =$$$ 11,因此 1 个字符的最大数量为 $$$2$$$。
- 在第二个查询中,$$$a =$$$ 111,因此 1 个字符的最大数量为 $$$3$$$。

在第二个测试用例中:

- 在第一个查询中,$$$a =$$$ 101 和 $$$b =$$$ 110。无法执行任何操作,因此 1 个字符的最大数量为 $$$2$$$。
- 在第二个查询中,$$$a =$$$ 1010 和 $$$b =$$$ 1101。由于 $$$a_2 = a_4 =$$$ 0,我们可以分配 $$$b_3 :=$$$ 1。现在 $$$b_1 = b_3 =$$$ 1,所以我们可以分配 $$$a_2 :=$$$ 1. 字符串$$$a$$$变为1110,因此1个字符的最大数量为$$$3$$$。