#P5535. 好串
好串
P5535 好串
题目描述
对于一个仅包含 0 和 1 的字符串 ,定义 为其所有二进制位的异或和。例如:
- ;
- ;
- ;
- 。
若一个 01 串 满足以下两个条件,则称其为好串:
-
是 的非负整数次幂。
-
存在两个非负整数 ,使得对所有 ,都有
$$s_i=f(i\operatorname{\ AND\ }x)\operatorname{\ XOR\ }b.$$
其中,下标从 开始;AND 表示整数按位与运算,XOR 表示按位异或运算; 是整数 的二进制表示中所有位的异或和。
你可以对一个 01 串进行区间取反操作:选择一段 (),将区间中每一位的 0 变为 1,1 变为 0。每次操作的代价为 。
现在给定长度为 的 01 串 ,以及 次相互独立的询问。对于每个询问 ,求把子串 变为某个好串所需的最少区间取反操作次数。
注意:每个询问仅考虑对应子串;变换过程不修改原串,所有询问相互独立。判断子串是否为好串时,子串内部从 重新编号。
输入格式
第一行包含一个整数 。
第二行包含一个长度恰为 的 01 串 。
第三行包含一个整数 。
接下来 行,每行包含两个整数 ,表示一次询问。保证 是 的非负整数次幂,且下标从 开始。
输出格式
输出 行,每行一个整数,表示对应询问的最少区间取反次数。
样例输入
8
00000101
3
0 7
2 5
0 3
样例输出
2
1
0
数据范围
对于 的数据:
- ;
- ;
- 是 的非负整数次幂;
- 只含
0和1。
长度为 的子串本身总是好串,答案为 。