Задача №115151. Вычислительная машина
У Саши есть две бинарные строки \(s\) и \(t\) одинаковой длины \(n\), состоящие из символов 0 и 1 .
Также есть вычислительная машина, которая умеет выполнять два вида операций с бинарными строками \(a\) и \(b\) одинаковой длины:
- Если \(a_{i} = a_{i + 2} =\) 0 , то можно присвоить \(b_{i + 1} :=\) 1 .
- Если \(b_{i} = b_{i + 2} =\) 1 , то можно присвоить \(a_{i + 1} :=\) 1 .
Саше стало интересно следующее: если рассмотреть строку \(a=s_ls_{l+1}\ldots s_r\) и строку \(b=t_lt_{l+1}\ldots t_r\), то какое максимальное количество символов 1 в строке \(a\) можно получить с помощью вычислительной машины. Так как Саша очень любознательный, но ленивый, то вам предстоит ответить на этот вопрос для нескольких интересующих его пар \((l_i, r_i)\).
В первой строке вводится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — длина строк \(s\) и \(t\).
Во второй строке вводится строка \(s\) длины \(n\), состоящая из нулей и единиц.
Во третьей строке вводится строка \(t\) длины \(n\), состоящая из нулей и единиц.
В четвертой строке вводится одно целое число \(q\) (\(1 \le q \le 200\,000\)) — количество запросов.
В следующих \(q\) строках описаны запросы. \(i\)-й запрос задается числами \(l_{i}\) и \(r_{i}\) (\(1 \le l_{i} \le r_{i} \le n\)).
Для каждого запроса выведите ответ на задачу.
В первом запросе \(a =\) 0100 , \(b = \) 1011 . Так как \(a_{1} = a_{3} = \) 0 , то можно присвоить \(b_{2} := \) 1 . Теперь \(b_{2} = b_{4} = \) 1 , поэтому можно присвоить \(a_{3} := \) 1 . Строка \(a\) стала равна 0110 , количество символов 1 равно двум. Можно показать, что это максимальное количество.
Во втором запросе \(a =\) 1000 , \(b = \) 1011 . \(b_{1} = b_{3} = \) 1 , поэтому можно присвоить \(a_{2} := \) 1 . Строка \(a\) стала равна 1100 . Увеличить число единиц в ней невозможно.
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла.
Решения, корректно работающие при \(n \le 300\), наберут не менее \(34\) баллов.
Решения, корректно работающие при \(n \le 5000\), наберут не менее \(60\) баллов. Дополнительно, решения, корректно работающие, когда \(s\) устроена как строка « 1100 » или « 0011 », повторенная несколько раз подряд, наберут не менее \(16\) баллов.
8 10001001 10110111 5 4 7 1 4 6 8 5 5 1 8
2 2 2 1 7