Разбор Div. B

# Разбор Div. B > Дорешка по разбору - самое важное в СП. Если вы не дорешиваете, вы ничему не учитесь. :::warning Совет: не лезьте в разбор сразу же. В идеале, подумайте над задачей где-то 20-30 минут, и только потом читайте разбор. ::: # [A. Улица Сталеваров](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/A) :::spoiler Разбор :::info Сначала давайте посчитаем количество каждого числа и запишем эти количества в отдельный вектор. Далее будем решать задачу для этого вектора. Оптимальная стратегия: применять операцию к двум наибольшим числам. Если наибольшее число больше суммы всех остальных, то оптимально всегда применять операцию только к нему и остальным числам. Значит, останется только это число минус сумма остальных, и это и будет ответом. Иначе ответ ВСЕГДА будет равен $n$ по по модулю 2 (доказывается). P.S. Знаю, что выглядит, как плохая задача, но это баян. Вам это может понадобиться на других олимпах. ::: # [B. 92](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/B) :::spoiler Подсказка 1 :::info Кажется, сравнить дроби, используя long double, не получится. Вспомните о компараторе и __int128_t. ::: :::spoiler Подсказка 2 :::info Если $\frac{a}{b} < \frac{c}{d}$, то $a*c<b*d$. ::: :::spoiler Разбор :::info Кажется, сравнить дроби, используя long double, не получится. Воспользуемся компаратором. Если $\frac{a}{b} < \frac{c}{d}$, то $a*c<b*d$. Значит, давайте найдём эти значения и сравним их в компараторе, а если они равны, сравним их индексы. WA 13: используйте __int128_t везде. Если что, long long * long long = long long, а не __int128_t WA 33: не забудьте про индексы! Асимптотика: $O(q \cdot log(n))$. ::: # [C. Декартово дерево (кладбище самолётов)](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/C) :::spoiler Шапка ordered_set :::info ```cpp #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using iset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; int main() { iset<int> st; } ``` ::: :::spoiler Подсказка :::info Старый добрый ordered set. Вспомните операции, которые он умеет делать. ::: :::spoiler Разбор :::info Воспользуемся структурой данных ordered set. Она умеет добавлять и удалять числа в множестве (insert и erase), считать количество чисел в сете строго меньших, чем $x$ (st.order_of_key(x)) и находить элемент по его номеру в возрастающем порядке (*st.find_by_order(x)). Асимптотика: $O(q \cdot log(n))$. ::: # [E. Серёжа](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/E) :::spoiler Подсказка 1 :::info Простые числа встречаются довольно часто. Если $x$ до $10^9$, то гарантируется, что уже через 200 (возможно, даже меньше) чисел после $x$ вы найдёте хотя бы одно простое. ::: :::spoiler Подсказка 2 :::info Наибольший делитель числа $x$ равен $\frac{x}{min}$, где $min$ - минимальный делитель $x$. За $\sqrt{n}$ искать делитель слишком долго. Думайте. ::: :::spoiler Подсказка 3 :::info Во втором запросе используется решето за линию. ::: :::spoiler Разбор :::info Простые числа встречаются довольно часто. Если $x$ до $10^9$, то гарантируется, что уже через 200 (возможно, даже меньше) чисел после $x$ вы найдёте хотя бы одно простое. Так что при ответе на первый запрос достаточно перебирать числа, начиная с $x$, пока не найдём простое. Проверка числа на простоту работает за $O(\sqrt{x})$. Запросов первого типа не более тысячи, так что это работает быстро. Наибольший делитель числа $x$ равен $x/min$, где $min$ - минимальный делитель $x$. За $\sqrt{n}$ искать делитель слишком долго. Так как во втором запросе число $x$ до $10^7$, воспользуемся решетом за линию. В полученном в нём массиве $lp$ будет находиться наименьший делитель числа. В итоге, ответ равен $\frac{x}{lp_x}$. Асимптотика: $O(q \cdot \sqrt{x})$. ::: # [F. Офисный стиляга](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/F) :::spoiler Совет :::info Сначала решите задачу C из этого контеста. В разборе на неё лежит шапка одной важной структуры. ::: :::spoiler Разбор :::info Воспользуемся структурой данных ordered set. Она умеет добавлять и удалять числа в множестве (insert и erase), считать количество чисел в сете строго меньших, чем $x$ (st.order_of_key(x)) и находить элемент по его номеру в возрастающем порядке (*st.find_by_order(x)). Асимптотика: $O(q \cdot log(n))$. ::: # [G. Все мои друзья](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/G) :::spoiler Подсказка 1 :::info Решите задачу для степеней двойки, используя каждый делитель не более одного раза. ::: :::spoiler Разбор. Часть 1 :::info Пусть текущее число - $x$, являющееся степенью двойки. Будем отнимать от него $\frac{x}{2}$, пока оно не станет равным $1$. Число $\frac{x}{2}$ всегда будет различным, так что мы используем каждыф делитель не более раза. ::: :::spoiler Подсказка 2 :::info Нужно научиться сводить любое число $x$ к степени двойки, используя делители не более одного раза. Это тоже можно сделать, используя степени двойки. Заметим, что $x$ всегда будет делиться на $2^{num}$, где $num$ - позиция младшего единичного бита. ::: :::spoiler Разбор. Часть 2 :::info Нужно научиться сводить любое число $x$ к степени двойки, используя делители не более одного раза. Это тоже можно сделать, используя степени двойки. Заметим, что $x$ всегда будет делиться на $2^{num}$, где $num$ - позиция младшего единичного бита. При выборе $2^{num}$ как делителя число незначительно изменится - единица в младшем единичном бите изменится на ноль. Значит, позиция младшего единичного бита после операции будет больше, чем до операции. Именно поэтому здесь мы тоже используем каждый делитель не более раза. В конечном итоге мы придём к числу с одним битом, а это будет степень двойки. Соединив части 2 и 1, получаем решение, приводящее к единице и использующее один и тот же делитель не более двух раз. Асимптотика: $O(n)$. ::: # [H. Рустем](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/H) :::spoiler Подсказка 1 :::info После применения операции произведения не меняется ::: :::spoiler Рабор :::info Факторизация произведения всего массива не меняется, значит мы хотим проверить, можно ли распределить все простые основания, так что бы $a_i$ были равны, это можно сделать если количество каждого из простых оснований делится на $n$. ::: ::: # [I. Песня для девочек](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/I) :::spoiler Подсказка 1 :::info Посчитаем массив префиксных сумм $pref$. Тогда сумма на отрезке $[l; r]$ равна $0$ если $pref_{l-1} = pref_r$. ::: :::spoiler Подсказка 2 :::info Если отрезок $[l; r]$ --- хороший, то отрезок $[l + 1; r]$ --- тоже хороший. Если отрезок $[l; r]$ --- плохой, то отрезок $[l - 1; r]$ --- тоже плохой. ::: :::spoiler Подсказка 3 :::info Для фиксированного $r$ будет существовать такое $k \le r$, что все отрезки $[l; r]$ при $l > k$ --- хорошие, а при $l \le k$ --- плохие. ::: :::spoiler Подсказка 4 :::info Переберём $r$. Тогда $k$ равно максимальному $a$, такому что $pref_a = pref_b$ и $a < b \le r$. Как быстро поддерживать текущее $k$? ::: :::spoiler Разбор :::info Заметим, что если отрезок $[l; r]$ --- хороший, то отрезок $[l + 1; r]$ --- тоже хороший, а если отрезок $[l; r]$ --- плохой, то отрезок $[l - 1; r]$ --- тоже плохой. Значит, для фиксированного $r$ будет существовать такое $k \le r$, что все отрезки $[l; r]$ при $l > k$ --- хорошие, а при $l \le k$ --- плохие. Посчитаем массив префиксных сумм $pref$ и переберём $r$. Тогда текущее $k$ равно максимальному $a$ такому, что $pref_a = pref_b$ (сумма на отрезке $[a + 1; b]$ равна $0$) и $a < b \le r$. Чтобы искать $k$, будем поддерживать map $mp[sum] = pos$, где $sum$ --- сумма на префиксе, а $pos$ --- позиция самого правого префикса с такой суммой. Тогда при обработке префикса $r$ присвоим $k = max(k, mp[pref[r]])$. Добавим к ответу $r - k$. ::: # [J. подворотня - мой дом](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/rubbish3) :::spoiler Подсказка 1 :::info Сначала давайте рассмотрим префиксные суммы до $m$-й. Допустим, среди них есть префиксная сумма, которая меньшая, чем $m$-я, и эта сумма считается на $i$-м префиксе. Какое условие выполняется для отрезка от $i+1$ до $m$? ::: :::spoiler Подсказка 2 :::info Если сумма на префиксе длины $i$ меньше, чем на префиксе длины $j$, и $i < j$, то сумма чисел на отрезке $(i + 1, j)$ больше нуля. Значит, чтобы $m$-я сумма была наименьшей, нужно за минимальное количество действий сделать так, чтобы все суммы вида $(i, m)$ были больше либо равны нулю. Осталось найти оптимальную стратегию. ::: :::spoiler Подсказка 3 :::info Как решать задачу для префиксов длины более $m$? Решение очень похоже на решение из подсказок 1 и 2. Если сумма на префиксе длины $i$ меньше, чем на префиксе длины $j$, и $i > j$, то... ::: :::spoiler Разбор :::info Если сумма на префиксе длины $i$ меньше, чем на префиксе длины $j$, и $i < j$, то сумма чисел на отрезке $(i + 1, j)$ больше нуля. Значит, чтобы $m$-я сумма была наименьшей, нужно за минимальное количество действий сделать так, чтобы все суммы вида $(i, m)$ были больше либо равны нулю. Чтобы сделать это оптимально, давайте будем идти по числам от $m$-го назад и поддерживать сумму чисел, а так же сами числа (т.к. числа могут повторяться, и нам в решении понадобится нахождение минимума в множестве, можно воспользоваться multiset). Добавим текущее число в множество. Если текущая сумма меньше нуля, то нам нужно сделать её больше либо равной нулю за оптимальное кол-во действий. На самом деле, можно доказать, что с помощью такой стратегии нам будет выгодно заменить ровно одно число. Логично, что чем меньше мы возьмём число, тем больше станет сумма, что в дальнейшем может уменьшить кол-во операций. Поэтому, если текущая сумма меньше нуля, просто возьмём наименьшее число из множества и заменим его на противоположное, обновив сумму. Важная деталь: не нужно делать операцию для отрезка $(1, m)$, если его сумма меньше нуля, ведь это и есть префиксная сумма длины $m$. Что делать с префиксами длины более $m$? На самом деле, решение тут очень похоже на то, что мы делали до этого. Если сумма на префиксе длины $i$ меньше, чем на префиксе длины $j$, и $i > j$, то сумма чисел на отрезке $(j + 1, i)$ меньше нуля. Так что давайте проделаем то же самое, но уже с отрезками вида $(m + 1, i)$. Если сумма отрезка больше нуля, заменим наименьшее число в отрезке на противоположное. Асимптотика: $O(n \cdot log (n))$. ::: . . . :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ :::spoiler НЕ ОТКРЫВАТЬ ![](https://hackmd.io/_uploads/ryNhBiLfT.png) :::