---
# System prepended metadata

title: Разбор 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)
:::
