量子计算 - 题目详情

题目背景

Y 同学正在设计一种新型的量子计算设备。该设备的核心是一个由两行平行的量子比特（qubit）链构成的计算单元。这两条链，分别称为 $S$ 链和 $T$ 链，可以通过一种特殊的“纠缠催化”反应来相互影响，改变各自的状态。

给定两个长度为 $N$ 的二进制字符串 $S$ 和 $T$ （即只包含字符 '0' 和 '1'）。

现在有 $Q$ 次独立的查询。每次查询给出一个区间 $[l, r]$ （下标从 1 开始）。我们关注 $S$ 和 $T$ 在这个区间上的子串，分别记为 $a = S[l \dots r]$ 和 $b = T[l \dots r]$ 。

在子串 $a$ 和 $b$ 上，可以进行任意次（零次或多次）以下两种“催化”操作：

$S \to T$ 催化: 如果在当前的子串 $a$ 中，存在某个位置 $i+1$ ( $l \le i < i+2 \le r$ )，其两侧的字符 $a_i$ 和 $a_{i+2}$ 均为 '0'，那么你可以将 $b$ 串中对应位置的字符 $b_{i+1}$ 变为 '1'。
$T \to S$ 催化: 如果在当前的子串 $b$ 中，存在某个位置 $i+1$ ( $l \le i < i+2 \le r$ )，其两侧的字符 $b_i$ 和 $b_{i+2}$ 均为 '1'，那么你可以将 $a$ 串中对应位置的字符 $a_{i+1}$ 变为 '1'。

操作会改变子串的状态，并可能引发新的操作。你需要对每个查询独立计算：在经过一系列最优的操作后，子串 $a$ 中最多可以包含多少个 '1'？

本题包含多组测试用例。

第一行包含一个整数 $T$ ，表示测试用例的数量。

对于每组测试用例：第一行包含一个整数 $N$ 。第二行和第三行分别包含字符串 $S$ 和 $T$ 。第四行包含一个整数 $Q$ 。接下来 $Q$ 行，每行包含两个整数 $l, r$ ，描述一次查询。

对于每次查询，输出一行一个整数，表示答案。