CF1978E Computing Machine

给定长度为 $n$ 的二进制字符串 $s,t$，串内只包含 $0$ 和 $1$，现有 $q$ 次询问，每次给出一个区间 $[l,r]$，分别记 $s,t$ 在 $[l,r]$ 上的子串为 $a,b$，进行任意次如下两种操作： - 若 $\exist i,i+2\in[l,r]$ 使得 $a_i=a_{i+2}=0$，则可以使 $b_{i+1}$ 的值变为 $1$。 - 若 $\exist i,i+2\in[l,r]$ 使得 $b_i=b_{i+2}=1$，则可以使 $a_{i+1}$ 的值变为 $1$。 现求所有操作结束后，串 $a$ 内最多可以包含多少 $1$。

一个测试点包含多组测试数据，第一行给出 $t(1\leq t \leq 10^4)$，表示测试数据组数。 对于每组数据： 第一行给出一个整数 $n(1\leq n \leq 2\times 10^5)$。 第二、三行给出两个二进制字符串 $s,t$。 第四行给出一个整数 $q$ 表示询问个数。 接下来 $q$ 行，每行两个整数 $l,r$，表示询问区间为 $[l,r]$。 保证 $\sum n$ 和 $\sum q$ 均不超过 $2 \times 10 ^ 5$。

$q$ 行，每行一个整数，表示对应询问的答案。

In the first test case: - In the first query, $ a = $ 11, so the maximum number of 1 characters is $ 2 $ . - In the second query, $ a = $ 111, so the maximum number of 1 characters is $ 3 $ . In the second test case: - In the first query, $ a = $ 101 and $ b = $ 110. No operations can be performed, so the maximum number of 1 characters is $ 2 $ . - In the second query, $ a = $ 1010 and $ b = $ 1101. Since $ a_2 = a_4 = $ 0, we can assign $ b_3 := $ 1. Now $ b_1 = b_3 = $ 1, so we can assign $ a_2 := $ 1. The string $ a $ becomes 1110, so the maximum number of 1 characters is $ 3 $ .