Задача №114484. Линеаризация
Побитовое «и» (and) двух целых неотрицательных чисел устроено следующим образом: запишем оба числа в двоичной системе счисления, \(i\)-й двоичный разряд результата равен \(1\), если у обоих аргументов он равен \(1\). Например, \((14\) \(and\) \(7) = (1110_2\) \(and\) \(0111_2) = 110_2 = 6\).
«Исключающее или» (xor) двух двоичных цифр равно \(1\), если они различны, и \(0\), если они равны. Таким образом, \(0\) \(xor\) \(0 = 0\), \(0\) \(xor\) \(1 = 1, 1\) \(xor\) \(0 = 1\) и \(1\) \(xor\) \(1 = 0\).
Функция четности \(P(x)\) для целого неотрицательного числа \(x\) равна \(1\), если в двоичной записи числа \(x\) нечетное число единичных разрядов, либо \(0\), если в двоичной записи \(x\) четное число единичных разрядов. Например, \(P(5) = P(101_2) = 0\), \(P(7) = P(111_2) = 1\).
Рассмотрим строку из нулей и единиц, длина которой является степенью двойки: \(s = s_0s_1\ldots s_{n-1}\), где \(n = 2^k\). Будем называть строку линейной, если найдется такое число \(x\), \(0 \le x < n\), и такая двоичная цифра \(b\), что для всех \(i\) от \(0\) до \(n-1\) выполнено \(s_i = P(i\) \(and\) \(x)\) \(xor\) \(b\).
Например, строка «1100» является линейной: выберем \(x = 2 = 10_2\) и \(b = 1\).
- \(s_0 = P(0\) \(and\) \(2)\) \(xor\) \(1 = P(0)\) \(xor\) \(1 = 0\) \(xor\) \(1 = 1\);
- \(s_1 = P(1\) \(and\) \(2)\) \(xor\) \(1 = P(0)\) \(xor\) \(1 = 0\) \(xor\) \(1 = 1\);
- \(s_2 = P(2\) \(and\) \(2)\) \(xor\) \(1 = P(2)\) \(xor\) \(1 = 1\) \(xor\) \(1 = 0\);
- \(s_3 = P(3\) \(and\) \(2)\) \(xor\) \(1 = P(2)\) \(xor\) \(1 = 1\) \(xor\) \(1 = 0\).
Строка же «0001» не является линейной: какое бы значение \(x\) мы ни выбрали, выполнено равенство \(P(0\) \(and\) \(x) = P(0) = 0\), значит \(b = 0\). Но \(0 = P(1\) \(and\) \(x)\) и \(0 = P(2\) \(and\) \(x)\), следовательно \(x = 0\). Однако \(P(3\) \(and\) \(0) = 0 \ne s_3 = 1\).
Пусть задана строка из нулей и единиц. За одно действие разрешается взять отрезок подряд идущих символов в строке и заменить их на противоположные: нули на единицы, а единицы на нули. Назовём трудностью линеаризации строки минимальное количество действий, за которое её можно сделать линейной.
Трудность линеаризации строки «0001», например, равна 1: можно инвертировать отрезок с 0-го по 2-й символ, получится строка «1111», которая является линейной с \(x = 0\), \(b = 1\). Есть и другие способы сделать эту строку линейной за 1 действие.
Задана строка \(t\) и \(q\) запросов \((l_i, r_i)\). Для каждого запроса рассмотрим в качестве строки \(s\) подстроку строки \(t\) с \(l_i\)-го по \(r_i\)-й символ, включительно. Символы строки \(t\) пронумерованы от начала, начиная с \(0\). Гарантируется, что длина каждой строки-запроса является степенью двойки. Требуется выяснить трудность линеаризации каждой такой подстроки.
Первая строка входных данных содержит число \(m\) — длину строки \(t\) (\(1 \le m \le 200\,000)\). Вторая строка содержит строку \(t\), она имеет длину \(m\) и состоит из нулей и единиц.
Следующая строка содержит число \(q\) — количество запросов (\(1 \le q \le 200\,000\)). Каждая из следующих \(q\) строк содержит по два целых числа: \(l_i\) и \(r_i\) (\(0 \le l_i \le r_i < m\), \(r_i - l_i + 1 \ge 2\) и является степенью двойки).
Для каждого запроса выведите одно число: трудность линеаризации соответствующей подстроки строки \(t\).
В примере в первом запросе требуется линеаризовать всю строку. Это можно сделать, например, инвертировав отрезок с \(4\)-го по \(6\)-й символ, получив строку «00001011», и затем инвертировав \(5\)-й символ, получив строку «00001111». Она является линейной с \(x = 4\) и \(b = 0\).
Во втором запросе необходимо линеаризовать строку «0001», это можно сделать за 1 действие, как описано в условии.
В третьем запросе необходимо линеаризовать строку «0000», которая и так является линейной для \(x = 0\), \(b = 0\).
8 00000101 3 0 7 2 5 0 3
2 1 0