F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5535. -- String

5535: String

Time Limit: 5 Sec  Memory Limit: 512 MB
Submit: 6  Solved: 2
[Submit][Status][Discuss]

Description

对于一个01串s,定义函数f(s)为s每一位的异或和,例如f(111)=1,f(110)=0,f(101)=0,f(100)=1。
一个01串s是好串,当且仅当其满足以下条件:
串的长度为2的幂次方。
存在两个非负整数x,b,使得i∈[0,|s|-1],si=f(i and x)xorb
(下标从0开始,此处f函数计算的是i and x对应的二进制串的值)。
现对于一个01串,可以使用区间取反操作,即选定一个区间[l,r],0≤l≤r<|s|,
并将[l,r]中的每一位取反(即1→0,0→1)。
现在给出一个长度为n的01串s,q次询问子串sl,r最少经过多少次区间取反操作变成好串

Input

第一行包含一个整数n。
第二行包含一个长为n的01串s。
第三行包含一个整数q。
接下来q行每行两个整数表示l,r。保证子串的长度为2的幂次方,且下标从0开始。
n,q≤5000

Output

输出q行,对于每个询问输出对应的答案

Sample Input

8
00000101
3
0 7
2 5
0 3

Sample Output

2
1
0

HINT

Source

[Submit][Status][Discuss]

HOME Back