U531625 好串

### 题目描述 对于一个 01 串 $s$，定义函数 $f(s)$ 为 $s$ 每一位的异或和，例如 $f(111) = 1, f(110) = 0, f(101) = 0, f(100) = 1$。 一个 01 串 $s$ 是好串，当且仅当其满足以下条件： 1、串的长度为 $2$ 的幂次方。 2、存在两个整数 $x\in N, b\in\{0,1\}$，使得 $∀i ∈ [0, |s| − 1], s_i = f(i\& x)\oplus b$（ $s$ 下标从 0 开始，$\&,\oplus$ 分别为二进制下的与、异或运算）。 现在给出一个长度为 $n$ 的 01 串 $s$，$q$ 次询问子串 $s[l,r]$：最少经过多少次区间取反操作可以将 $s[l,r]$ 变成好串。 区间取反操作：即选定一个区间 $[l, r], 1 ≤ l ≤ r ≤ |s|$， 并将 $[l, r]$ 中的每一位取反（$1 → 0, 0 → 1$）。 ### 输入格式 第一行包含一个整数 $n$。 第二行包含一个长为 $n$ 的 01 串 $s$。 第三行包含一个整数 $q$。 接下来 $q$ 行每行两个整数表示 $l, r$。保证子串的长度为 $2$ 的幂次方。 子串下标从 $0$ 开始。 ### 输出格式 输出 $q$ 行，对于每个询问输出对应的答案。 ### 样例 #### 1.in 8 00000101 3 0 7 2 5 0 3 #### 1.out 2 1 0 #### 2.in 见下发文件 #### 2.out 见下发文件 ### 数据范围 共 $25$ 个测试点。 测试点 $1—5$ ：满足 $n, q ≤ 8$； 测试点 $6—10$： $n, q ≤ 16$，分值 $20$ 分。 测试点 $11—19$： 满足 $n, q ≤ 5000$，分值 50 分。 对于所有数据，均满足 $n, q ≤ 2\times10^5$。

无

无

无