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


可复制的 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