Всем Привет!↵
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать очередной пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://codeforces.me/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражнения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из своей головы и записали/нарисовали максимальное количество идей и больше уже ничего не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерировать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен к разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Искандер и рисунки↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Рассмори одну полоску длины $k$ из символов '#'. Сколько времени нужно, чтобы ее стереть? Что происходит за одну секунду?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
За одну секунду мы стираем 2 символа '#' (или 1, если был всего один символ). Тогда через сколько времени мы все сотрем?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Через $\lceil\frac{k}{2}\rceil$ секунд. Тогда чему равен ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Мы должны найти самую длинную полоску из подряд идущих символов '#' и вычислить ответ по формуле из предыдущего шага.↵
</spoiler>↵
↵
Решение: [submission:382817545]↵
↵
B. Никита и книги↵
===================↵
↵
<spoiler summary="Шаг 1">↵
В условии написано, что мы можем перекладывать единицы слева направо, тогда что логичнее всего можно сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Логичнее всего строить последовательность слева направо. Пойдем слева направо. Пусть мы стоим в позиции $i$, тогда какую оптимальную высоту мы хотим получить здесь?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Какое ограничение снизу на $a_i$ мы можем записать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Запишем последовательность $(1,2,\ldots, n)$ -- это возрастающая последовательность с минимальными выстоами башен, тогда $a_i \ge i$, то есть мы хотим сделать $a_i$ равным $i$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Тогда будем поддерживать количество единиц $S$, которые мы можем перенести с башен до $i$-й. Что делаем, если $a_i > i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Если $a_i > i$, тогда мы можем увеличить $S$ на $(a_i - i)$ и пойти дальше (и уменьшить $a_i$ до $i$).↵
А что если $a_i < i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Тогда нам нужно увелчить высоту башни, потратив $(i - a_i)$. Тогда если $S < (i - a_i)$, то ответа нет, а иначе уменьшаем $S$ на $(i - a_i)$ и идем дальше.↵
</spoiler>↵
↵
Решение: [submission:382818009]↵
↵
C. Стёпа и перестановка↵
===================↵
↵
<spoiler summary="Шаг 1">↵
В задачах на сортировку очень часто помогает придумать способ обменять местами какие-то две элемента $(i,j)$. Попробуем поприменять описанные в условии операции несколько раз.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Мы можем обменивать $(i, i + x)$ и $(i, i + y)$, тогда какие два элемента мы еще можем обменять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Тогда мы можем обменять $(i, i + x)$, дальше обменять $(i, i + y)$, а затем опять $(i, i + x)$, тогда мы по сути обменяли местами $(i + x, i + y)$ или другими словами $(i, i + (x - y))$. На что это похоже?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Как работает простейший алгоритм Евклида?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Алгоритм Евклида гласит, что $gcd(x, y) = gcd(x, y - x) = \ldots$. А если хотите больше узнать о нетривиальных применениях этого алгоритма, рекомендую прочитать [ЭТОТ ПОСТ](https://codeforces.me/blog/entry/153213) и присоединиться к нам в сообщество)↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Из шагов выше получаем, что мы можем обменять местами любые два индекса $(i,j)$, что $|i - j|$ делится на $gcd(x, y)$.↵
Как нам это помогает?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Это значит, что мы можем отсортировать подпоследовательности $i_1 < i_2 < \ldots$, которые имеют одинаковые остаток от деления на $gcd(x, y)$. Сдеаем это и проверим, что итоговая последовательность отсортировалась.↵
</spoiler>↵
↵
Решение: [submission:382818403]↵
↵
D. Ярослав и продуктивность↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Решим задачу попроще: допустим мы можем изменить знак любого префикса, чему тогда равен ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Тогда ответ равен \sum |a_i|, как его получить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Если $a_n < 0$, то мы можем поменять знак у префикса $[1 \ldots n]$ и перейти к вычислению ответа на массиве $(a_1,a_2,\ldots,a_{n-1})$, потому дальнейшие изменения никак не повлияют на $a_n$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Возвращаемся к нашей задаче. Какие элементы мы никогда не сможем изменить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Пусть $B = \max b_j$ — максимальный префикс, который мы можем изменить. Тогда все элемент $a_i$, что $i > B$ мы не можем изменить, значит мы можем добавить к ответу их сумму и забыть про них, теперь считаем, что мы можем поменять все элементы местами. Идем дальше. Какие элементы всегда будут меняться одинаково? (то есть нельзя изменить знак одного элемента без изменения второго)↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Пусть $b_1 < b_2 < \ldots < b_m$, тогда элементы $[1,b_1]$ всегда будут меняться одинаково, а еще какие?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Рассмотрим блоки $[1, b_1], [b_1+1,b_2], [b_2+1,b_3], \ldots,[b_{m-1}+1,b_m]$. Элементы в каждом блоке всегда будут меняться одинаково, тогда что мы можем сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Тогда мы можем вычислить сумму элементов в каждом блоке и перейти к задаче из Шага 1, тогда как посчитать ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Пусть $S_i$ — сумма элементов в блоке $[b_{i-1}+1,b_i]$, тогда ответ $\sum |S_i|$↵
</spoiler>↵
↵
Решение: [submission:382818882]↵
↵
E. Маша и гирлянда↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Давайте формально запишем, что то нас хотят в условии. Пусть $f_i = 1$, если $s_i = s_{i-1}$ и $f_i = 0$ иначе. Тогда что от нас хотят в условии? Что означает операция выбора отрезка $[l,r]$? Что при этом меняется и как?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Такая оперция изменяет $f_l$ с 0 на 1 и наоборот, а также меняет $f_{r+1}$ с 0 на 1 и наоборот. То есть по сути за одну операцию мы можем изменить какие-то два элемента $f_i,f_j$ (или один, если отрезок — это префикс или суффикс).↵
Как нам это помогает?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Пусть к нам пришел запрос $l,r,k$. Пусть $x = \sum_{i=l+1}^{r}f_i$. Тогда как определить ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
В таком случае минимальное количество операций равно $\lceil\frac{x}{2}\rceil$, остается сравнить его с $k$. А чтобы посчитать $x$ достаточно предподсчитать префиксные суммы.↵
</spoiler>↵
↵
Решение: [submission:382819665]↵
↵
F. Аня любит деревья!↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Рассмотрим некоторую вершину $v$ и ее поддерево, пусть в ее поддереве находятся числа $x_1<x_2<\ldots<x_l$. Какое свойство должно выполнятьcя?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Должно выполняться, что эти числа должны образовывать отрезок, как проверить это свойство?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Должно выполнться равенство $x_l-x_1+1=l$. Хорошо, осталось еще учесть то, что мы теперь можем циклически сдвигать всех сыновей.↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Мы хотим отсортировать все элементы, но мы можем делать только циклические сдвиги, а еще мы знаем, что все поддеревья хранят непрерывный отрезок чисел. Как тогда мы можем отсортировать эти числа?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Мы обязаны на первую позицию поставить поддерево с минимальным значением, остается только проверить, что это даст сортировку.↵
</spoiler>↵
↵
Решение: [submission:382820351]↵
↵
G. Юра и дедлайны↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Если нарисовать картинку, то можно заметить, что удобно работать с отрезками $(i - a_i, i + a_i)$, тогда что будет означать условие |i — j| > max(a_i, a_j)?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Пусть $i > j$, тогда условие переписывается как i > j + a_i И $i - a_i > j$, то есть никакой центр никакого отрезка не покрывается каким-то другим отрезком. Отлично, в задачах про отрезки важно спросить себя, могут ли быть вложенные отрезки?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Нет, не могут, т.к. иначе центр одного отрезка покровется бОльшим отрезком, тогда мы можем отсортировать отрезки по правой границе (по $i + a_i$). Что тогда? Пусть мы после сортировки выбрали отрезки $\ldots (l_1,r1), (l_2,r_2), (l_3, r_3)$, нужно ли нам проверять свойство выше для отрезков $(l_1,r1), (l_3,_r3)$, если мы знаем, что все соседние отрезки удовлетворяют условиям выше?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Нет, не нужно, потому что мы знаем, что центры отрезков $(l_1,r_1)$ и $(l_3,r_3)$ лежат по разные стороны от отрезка $(l_2,r_2)$, а значит не может быть так, что центр одного отрезка покрыт вторым отрезком, потому что $l_1 < l_2 < l_3$ и $r_1 < r_2 < r_3$, это удобное свойство возникает из-за того, что не может быть вложенных отрезков в ответе.↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
После сортировки логичным шагом является применение динамического программирования, стандартный подход в поиске подпоследовательностей максимальной длины с какими-то свойствами.↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Итак, допустим мы отсортировали отрезки по правой границе: $(l_1,r_1),(l_2,r_2),\ldots, (l_2,r_n)$. Тогда пусть $dp_i$ — длина максимальной подпоследовательности, заканчивающейся в $i$-м отрезке. Ответ равен $\max dp_i$. Изначально можем проставить $dp_i = 1$ для всех $i$. Осталось только придумать переход.↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Пусть центр $i$ — го отрезка равен $c_i = (l_i + r_i) / 2$↵
Пусть мы хотим посчитать $dp_i$. Тогда в медленном решении мы бы хотели перебрать $j < i$ , что $c_j < l_i$ и $r_j < c_i$. Что мы можем сделать? Как найти такие $j$, что $r_j < c_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Вспомним, что наши отрезки отсортированы по $r_i$, тогда мы можем бинарным поиском найти максмальное $q$, что $r_q < c_i$, тогда для всех $j \le q$ будет верно, что $r_j < c_i$. Осталось разобраться с условием $c_j < l_i$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
(возможно, есть вариант проще), но для этого я использую персистентное дерево отрезков. То есть я для каждого $i$ знаю дерево отрезков $T_i$, которое хранит в позициях $c_j$ значения $dp_j$ для всех $j \le i$. Тогда для обновления $dp_i$ мне достаточно найти максимум в префиксе $[0, l_i - 1]$ в ДО $T_q$.↵
</spoiler>↵
↵
Решение: [submission:382823231]↵
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать очередной пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://codeforces.me/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражнения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из своей головы и записали/нарисовали максимальное количество идей и больше уже ничего не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерировать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен к разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Искандер и рисунки↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Рассмори одну полоску длины $k$ из символов '#'. Сколько времени нужно, чтобы ее стереть? Что происходит за одну секунду?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
За одну секунду мы стираем 2 символа '#' (или 1, если был всего один символ). Тогда через сколько времени мы все сотрем?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Через $\lceil\frac{k}{2}\rceil$ секунд. Тогда чему равен ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Мы должны найти самую длинную полоску из подряд идущих символов '#' и вычислить ответ по формуле из предыдущего шага.↵
</spoiler>↵
↵
Решение: [submission:382817545]↵
↵
B. Никита и книги↵
===================↵
↵
<spoiler summary="Шаг 1">↵
В условии написано, что мы можем перекладывать единицы слева направо, тогда что логичнее всего можно сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Логичнее всего строить последовательность слева направо. Пойдем слева направо. Пусть мы стоим в позиции $i$, тогда какую оптимальную высоту мы хотим получить здесь?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Какое ограничение снизу на $a_i$ мы можем записать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Запишем последовательность $(1,2,\ldots, n)$ -- это возрастающая последовательность с минимальными выстоами башен, тогда $a_i \ge i$, то есть мы хотим сделать $a_i$ равным $i$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Тогда будем поддерживать количество единиц $S$, которые мы можем перенести с башен до $i$-й. Что делаем, если $a_i > i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Если $a_i > i$, тогда мы можем увеличить $S$ на $(a_i - i)$ и пойти дальше (и уменьшить $a_i$ до $i$).↵
А что если $a_i < i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Тогда нам нужно увелчить высоту башни, потратив $(i - a_i)$. Тогда если $S < (i - a_i)$, то ответа нет, а иначе уменьшаем $S$ на $(i - a_i)$ и идем дальше.↵
</spoiler>↵
↵
Решение: [submission:382818009]↵
↵
C. Стёпа и перестановка↵
===================↵
↵
<spoiler summary="Шаг 1">↵
В задачах на сортировку очень часто помогает придумать способ обменять местами какие-то две элемента $(i,j)$. Попробуем поприменять описанные в условии операции несколько раз.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Мы можем обменивать $(i, i + x)$ и $(i, i + y)$, тогда какие два элемента мы еще можем обменять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Тогда мы можем обменять $(i, i + x)$, дальше обменять $(i, i + y)$, а затем опять $(i, i + x)$, тогда мы по сути обменяли местами $(i + x, i + y)$ или другими словами $(i, i + (x - y))$. На что это похоже?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Как работает простейший алгоритм Евклида?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Алгоритм Евклида гласит, что $gcd(x, y) = gcd(x, y - x) = \ldots$. А если хотите больше узнать о нетривиальных применениях этого алгоритма, рекомендую прочитать [ЭТОТ ПОСТ](https://codeforces.me/blog/entry/153213) и присоединиться к нам в сообщество)↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Из шагов выше получаем, что мы можем обменять местами любые два индекса $(i,j)$, что $|i - j|$ делится на $gcd(x, y)$.↵
Как нам это помогает?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Это значит, что мы можем отсортировать подпоследовательности $i_1 < i_2 < \ldots$, которые имеют одинаковые остаток от деления на $gcd(x, y)$. Сдеаем это и проверим, что итоговая последовательность отсортировалась.↵
</spoiler>↵
↵
Решение: [submission:382818403]↵
↵
D. Ярослав и продуктивность↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Решим задачу попроще: допустим мы можем изменить знак любого префикса, чему тогда равен ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Тогда ответ равен \sum |a_i|, как его получить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Если $a_n < 0$, то мы можем поменять знак у префикса $[1 \ldots n]$ и перейти к вычислению ответа на массиве $(a_1,a_2,\ldots,a_{n-1})$, потому дальнейшие изменения никак не повлияют на $a_n$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Возвращаемся к нашей задаче. Какие элементы мы никогда не сможем изменить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Пусть $B = \max b_j$ — максимальный префикс, который мы можем изменить. Тогда все элемент $a_i$, что $i > B$ мы не можем изменить, значит мы можем добавить к ответу их сумму и забыть про них, теперь считаем, что мы можем поменять все элементы местами. Идем дальше. Какие элементы всегда будут меняться одинаково? (то есть нельзя изменить знак одного элемента без изменения второго)↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Пусть $b_1 < b_2 < \ldots < b_m$, тогда элементы $[1,b_1]$ всегда будут меняться одинаково, а еще какие?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Рассмотрим блоки $[1, b_1], [b_1+1,b_2], [b_2+1,b_3], \ldots,[b_{m-1}+1,b_m]$. Элементы в каждом блоке всегда будут меняться одинаково, тогда что мы можем сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Тогда мы можем вычислить сумму элементов в каждом блоке и перейти к задаче из Шага 1, тогда как посчитать ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Пусть $S_i$ — сумма элементов в блоке $[b_{i-1}+1,b_i]$, тогда ответ $\sum |S_i|$↵
</spoiler>↵
↵
Решение: [submission:382818882]↵
↵
E. Маша и гирлянда↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Давайте формально запишем, что то нас хотят в условии. Пусть $f_i = 1$, если $s_i = s_{i-1}$ и $f_i = 0$ иначе. Тогда что от нас хотят в условии? Что означает операция выбора отрезка $[l,r]$? Что при этом меняется и как?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Такая оперция изменяет $f_l$ с 0 на 1 и наоборот, а также меняет $f_{r+1}$ с 0 на 1 и наоборот. То есть по сути за одну операцию мы можем изменить какие-то два элемента $f_i,f_j$ (или один, если отрезок — это префикс или суффикс).↵
Как нам это помогает?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Пусть к нам пришел запрос $l,r,k$. Пусть $x = \sum_{i=l+1}^{r}f_i$. Тогда как определить ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
В таком случае минимальное количество операций равно $\lceil\frac{x}{2}\rceil$, остается сравнить его с $k$. А чтобы посчитать $x$ достаточно предподсчитать префиксные суммы.↵
</spoiler>↵
↵
Решение: [submission:382819665]↵
↵
F. Аня любит деревья!↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Рассмотрим некоторую вершину $v$ и ее поддерево, пусть в ее поддереве находятся числа $x_1<x_2<\ldots<x_l$. Какое свойство должно выполнятьcя?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Должно выполняться, что эти числа должны образовывать отрезок, как проверить это свойство?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Должно выполнться равенство $x_l-x_1+1=l$. Хорошо, осталось еще учесть то, что мы теперь можем циклически сдвигать всех сыновей.↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Мы хотим отсортировать все элементы, но мы можем делать только циклические сдвиги, а еще мы знаем, что все поддеревья хранят непрерывный отрезок чисел. Как тогда мы можем отсортировать эти числа?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Мы обязаны на первую позицию поставить поддерево с минимальным значением, остается только проверить, что это даст сортировку.↵
</spoiler>↵
↵
Решение: [submission:382820351]↵
↵
G. Юра и дедлайны↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Если нарисовать картинку, то можно заметить, что удобно работать с отрезками $(i - a_i, i + a_i)$, тогда что будет означать условие |i — j| > max(a_i, a_j)?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Пусть $i > j$, тогда условие переписывается как i > j + a_i И $i - a_i > j$, то есть никакой центр никакого отрезка не покрывается каким-то другим отрезком. Отлично, в задачах про отрезки важно спросить себя, могут ли быть вложенные отрезки?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Нет, не могут, т.к. иначе центр одного отрезка покровется бОльшим отрезком, тогда мы можем отсортировать отрезки по правой границе (по $i + a_i$). Что тогда? Пусть мы после сортировки выбрали отрезки $\ldots (l_1,r1), (l_2,r_2), (l_3, r_3)$, нужно ли нам проверять свойство выше для отрезков $(l_1,r1), (l_3,_r3)$, если мы знаем, что все соседние отрезки удовлетворяют условиям выше?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Нет, не нужно, потому что мы знаем, что центры отрезков $(l_1,r_1)$ и $(l_3,r_3)$ лежат по разные стороны от отрезка $(l_2,r_2)$, а значит не может быть так, что центр одного отрезка покрыт вторым отрезком, потому что $l_1 < l_2 < l_3$ и $r_1 < r_2 < r_3$, это удобное свойство возникает из-за того, что не может быть вложенных отрезков в ответе.↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
После сортировки логичным шагом является применение динамического программирования, стандартный подход в поиске подпоследовательностей максимальной длины с какими-то свойствами.↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Итак, допустим мы отсортировали отрезки по правой границе: $(l_1,r_1),(l_2,r_2),\ldots, (l_2,r_n)$. Тогда пусть $dp_i$ — длина максимальной подпоследовательности, заканчивающейся в $i$-м отрезке. Ответ равен $\max dp_i$. Изначально можем проставить $dp_i = 1$ для всех $i$. Осталось только придумать переход.↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Пусть центр $i$ — го отрезка равен $c_i = (l_i + r_i) / 2$↵
Пусть мы хотим посчитать $dp_i$. Тогда в медленном решении мы бы хотели перебрать $j < i$ , что $c_j < l_i$ и $r_j < c_i$. Что мы можем сделать? Как найти такие $j$, что $r_j < c_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Вспомним, что наши отрезки отсортированы по $r_i$, тогда мы можем бинарным поиском найти максмальное $q$, что $r_q < c_i$, тогда для всех $j \le q$ будет верно, что $r_j < c_i$. Осталось разобраться с условием $c_j < l_i$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
(возможно, есть вариант проще), но для этого я использую персистентное дерево отрезков. То есть я для каждого $i$ знаю дерево отрезков $T_i$, которое хранит в позициях $c_j$ значения $dp_j$ для всех $j \le i$. Тогда для обновления $dp_i$ мне достаточно найти максимум в префиксе $[0, l_i - 1]$ в ДО $T_q$.↵
</spoiler>↵
↵
Решение: [submission:382823231]↵
