← 返回题目列表

Codeforces · 1090/H

H. 线性化

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Linearization - 原题 PDF 第 1 页
原题PDF第11页
Linearization - 原题 PDF 第 2 页
原题PDF第12页
可复制的 PDF 提取文本
XIX Russia Team Open, High School Programming Contest
              St Petersburg, Barnaul, Tbilisi, Almaty, Kremenchug, Sochi, December 9, 2018
Problem H. Linearization

    Time limit:        2 seconds
    Memory limit:     512 megabytes

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 and 7) = (11102 and 01112) = 1102 = 6.

“Exclusive or” (xor) of two binary digits equals 1  if they are unequal, and 0  if they are equal. Thus,
0 xor 0 = 0, 0 xor 1 = 1, 1 xor 0 = 1 and 1 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(1012) = 0,
P(7) = P(1112) = 1.
Consider a binary string whose length is a power of two: s = s0s1 . . . sn−1, where n = 2k. We will call this
string linear, if there is an integer x, 0 ≤x < n, and a binary digit b, such that for all i from 0 to n −1
holds si = P(i and x) xor b.

For example, a string “1100” is linear: take x = 2 = 102 and b = 1.

        • s0 = P(0 and 2) xor 1 = P(0) xor 1 = 0 xor 1 = 1
        • s1 = P(1 and 2) xor 1 = P(0) xor 1 = 0 xor 1 = 1
        • s2 = P(2 and 2) xor 1 = P(2) xor 1 = 1 xor 1 = 0
        • s3 = P(3 and 2) xor 1 = P(2) xor 1 = 1 xor 1 = 0

Meanwhile, “0001” is not linear: whatever x we chose, we would have P(0 and x) = P(0) = 0, therefore
b = 0. We have 0 = P(1 and x) and 0 = P(2 and x), therefore x = 0. But P(3 and 0) = 0 ̸= s3 = 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 (li, ri). For each query, consider a substring of t from li-th digit to
ri-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.

Input

The first line of input contains a single integer m — the length of the string t (1 ≤m ≤200 000). The
second line contains a binary string t of length m.

The next line contains integer q — the number of queries (1 ≤q ≤200 000). Each of the next q lines
contains two integers, li and ri (0 ≤li ≤ri < m, ri −li + 1 ≥2, substring length is a power of two).

Output

For each query, print one integer: the hardness of linearization of the corresponding substring of t.





                                        Page 11 of 18

XIX Russia Team Open, High School Programming Contest
              St Petersburg, Barnaul, Tbilisi, Almaty, Kremenchug, Sochi, December 9, 2018

Example

             standard input                         standard output
 8                                       2
 00000101                                1
 3                                       0
 0 7
 2 5
 0 3

Note

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.





                                        Page 12 of 18