#P5535. 好串

好串

P5535 好串

题目描述

对于一个仅包含 0 和 1 的字符串 ss,定义 f(s)f(s) 为其所有二进制位的异或和。例如:

  • f(111)=1f(111)=1;
  • f(110)=0f(110)=0;
  • f(101)=0f(101)=0;
  • f(100)=1f(100)=1。

若一个 01 串 ss 满足以下两个条件,则称其为好串:

  1. ∣s∣|s| 是 22 的非负整数次幂。

  2. 存在两个非负整数 x,bx,b,使得对所有 0≤i<∣s∣0\le i<|s|,都有

    $$s_i=f(i\operatorname{\ AND\ }x)\operatorname{\ XOR\ }b.$$

其中,下标从 00 开始;AND 表示整数按位与运算,XOR 表示按位异或运算;f(i AND ⁡x)f(i\operatorname{\ AND\ }x) 是整数 i AND ⁡xi\operatorname{\ AND\ }x 的二进制表示中所有位的异或和。

你可以对一个 01 串进行区间取反操作:选择一段 [l,r][l,r](0≤l≤r<∣s∣0\le l\le r<|s|),将区间中每一位的 0 变为 1,1 变为 0。每次操作的代价为 11。

现在给定长度为 nn 的 01 串 ss,以及 qq 次相互独立的询问。对于每个询问 [l,r][l,r],求把子串 slsl+1⋯srs_l s_{l+1}\cdots s_r 变为某个好串所需的最少区间取反操作次数。

注意:每个询问仅考虑对应子串;变换过程不修改原串,所有询问相互独立。判断子串是否为好串时,子串内部从 00 重新编号。

输入格式

第一行包含一个整数 nn。

第二行包含一个长度恰为 nn 的 01 串 ss。

第三行包含一个整数 qq。

接下来 qq 行,每行包含两个整数 l,rl,r,表示一次询问。保证 r−l+1r-l+1 是 22 的非负整数次幂,且下标从 00 开始。

输出格式

输出 qq 行,每行一个整数,表示对应询问的最少区间取反次数。

样例输入

8
00000101
3
0 7
2 5
0 3

样例输出

2
1
0

数据范围

对于 100%100\% 的数据:

  • 1≤n,q≤50001\le n,q\le 5000;
  • 0≤l≤r<n0\le l\le r<n;
  • r−l+1r-l+1 是 22 的非负整数次幂;
  • ss 只含 0 和 1。

长度为 11 的子串本身总是好串,答案为 00。