| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 5 | 1 | 1 | 100.000% |
Bitwise "and" of two non-negative integers is calculated as follows: write both numbers in binary, then the $i$-th binary digit of the result is equal to 1ドル$ if both arguments have the $i$-th digit equal to 1ドル$. For example, $(14 \text{ and } 7) = (1110_2 \text{ and } 0111_2) = 110_2 = 6$.
"Exclusive or" (xor) of two binary digits equals 1ドル$ if they are unequal, and 0ドル$ if they are equal. Thus, 0ドル \text{ xor } 0 = 0,ドル 0ドル \text{ xor } 1 = 1,ドル 1ドル \text{ xor } 0 = 1$ and 1ドル \text{ xor } 1 = 0$.
Parity function $P(x)$ for a non-negative integer $x$ equals 1ドル$ if the binary notation of $x$ has odd number of ones, and 0ドル$ if the binary notation of $x$ has even number of ones. For example, $P(5) = P(101_2) = 0,ドル $P(7) = P(111_2) = 1$.
Consider a binary string whose length is a power of two: $s = s_0s_1\ldots s_{n-1},ドル where $n = 2^k$. We will call this string linear, if there is an integer $x,ドル 0ドル \le x < n,ドル and a binary digit $b,ドル such that for all $i$ from 0ドル$ to $n-1$ holds $s_i = P(i \text{ and } x) \text{ xor } b$.
For example, a string "1100" is linear: take $x = 2 = 10_2$ and $b = 1$.
Meanwhile, "0001" is not linear: whatever $x$ we chose, we would have $P(0 \text{ and } x) = P(0) = 0,ドル therefore $b = 0$. We have 0ドル = P(1 \text{ and } x)$ and 0ドル = P(2 \text{ and } x),ドル therefore $x = 0$. But $P(3 \text{ and } 0) = 0 \ne s_3 = 1$.
Consider a binary string. In one action you can take a continuous segment of digits and invert them: change all zeros to ones and vice versa. Call hardness of linearization of this string the minimal number of actions one needs to make it linear.
For example, the hardness of linearization for the string "0001" is 1ドル$: you can invert the left three digits to get the string "1111" which is linear with $x = 0,ドル $b = 1$. There are other ways to linearize it in one action.
You are given a string $t$ and $q$ queries $(l_i, r_i)$. For each query, consider a substring of $t$ from $l_i$-th digit to $r_i$-th digit, inclusive. Digits of $t$ are numbered from left to right, starting with 0ドル$. It is guaranteed that the length of each query is a power of two. Calculate the hardness of linearization for every given substring.
The first line of input contains a single integer $m$ --- the length of the string $t$ (1ドル \le m \le 200,000円)$. The second line contains a binary string $t$ of length $m$.
The next line contains integer $q$ --- the number of queries (1ドル \le q \le 200,000円$). Each of the next $q$ lines contains two integers, $l_i$ and $r_i$ (0ドル \le l_i \le r_i < m,ドル $r_i - l_i + 1 \ge 2,ドル substring length is a power of two).
For each query, print one integer: the hardness of linearization of the corresponding substring of $t$.
8 00000101 3 0 7 2 5 0 3
2 1 0
In the first query we need to linearize the whole string. This can be done, for example, by inverting the segment from 4ドル$-th to 6ドル$-th digit, getting the string "00001011", and then inverting the 5ドル$-th digit, getting "00001111" which is linear with $x = 4$ and $b = 0$.
In the second query, the string "0001" can be linearized in one action, as described in the problem statement.
In the third query the string "0000" is already linear with $x = 0,ドル $b = 0$.