Задание №168969: Информация и кодирование

11 класс, 16.02.2026 Задача D. Хорошие палиндромы Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт Рассмотрим процесс на строке s, состоящей только из символов ”a” и ”b”. На каждом шаге этого процесса из строки одновременно удаляются первое и последнее вхождение букв ”a” и ”b” (если такие вхождения есть). Обратите внимание, что первое и последнее вхождение могут совпадать. Нас интересует первый момент, после которого строка s станет палиндромом. Палиндромом называется строка, которая читается одинаково слева-направо и справа-налево. Пустая строка считается палиндромом. Номер шага, после которого строка становится палиндромом, назовем красотой строки. Пусть s = "aabaababa". Первые и последние вхождения каждой буквы подчеркнуты. После первого шага процесса s = "aaaba". Здесь первое и последнее вхождение буквы ”b” совпадают. После второго шага процесса s = "aa это палиндром, поэтому красота s равна 2. Дана строка t, состоящая из символов ”a” и ”b”. Вам поступит q запросов двух типов: ! i — изменить i-й символ в t на другой ("a"меняется на "b"и наоборот). ? l r — узнать красоту подстроки t[l...r]. Обратите внимание, что запросы первого типа влияют на все последующие запросы, а запросы второго типа никак не меняют строку t. Формат входных данных В первой строке входных данных вводится строка t (1 ⩽ |t| ⩽ 2 · 105). Гарантируется, что t состоит только из букв "a"и "b". В следующей строке входных данных вводится единственное число q (1 ⩽ q ⩽ 2 · 105) — количество запросов. Следующие q строк содержат описания запросов. Описание каждого запроса имеет следующий вид: ! i (1 ⩽ i ⩽ n) — изменить символ в строке. ? l r (1 ⩽ l ⩽ r ⩽ n) — узнать красоту подстроки t[l...r]. Формат выходных данных Для каждого запроса второго типа выведите соответствующую красоту подстроки. Система оценки Решения, верно работающие при |t|,q ⩽ 100 будут набирать не менее 12 баллов. Решения, верно работающие при t = ”ababa...” и |t|,q ⩽ 100000 и без запросов первого типа будут набирать не менее 12 баллов. Решения, верно работающие при |t|,q ⩽ 5000 будут набирать не менее 28 баллов. Решения, верно работающие при |t|,q ⩽ 100000 и без запросов первого типа будут набирать не менее 35 баллов. Решения, верно работающие при |t|,q ⩽ 80000 будут набирать не менее 63 баллов. Страница 6 из 9 Высшая проба 2026