Оскільки кожен друг приносить по \(c\) яблук, Зеник отримає \(b \cdot c\) яблук від усіх друзів. Додавши їх до початкової кількості \(a\), одержуємо \(a + b \cdot c\).
В задачі задано дві умови: щоб загальна кількість підтягувань не була меншою \(m\) і щоб кількість підтягувань в кожному підході не була меншою за \(k\) . Мінімальна кількість підтягувань яку потрібно зробити за тренування щоб задовольнити другу умову — \(n\cdot k\). Отже мінімальна кількість підтягувань за тренування — \(min(n \cdot k, m)\).
В задачі нам потрібно знайти мінімальну кількість операцій зміни на рядках та стовпцях, щоб змогти дійти білим шляхом з правої верхньої клітинки до лівої нижньої. Для оптимального перефарбування дошки достатньо спочатку перефарбувати всі парні рядки, а потім всі парні стовпці. В результаті таких операцій вся дошка стане білою. Отже, відповідь до задачі \(\lfloor \frac{n}{2} \rfloor + \lfloor \frac{m}{2} \rfloor\).
Очевидно, що максимум і мінімум оптимального підвідрізка будуть стояти саме на його межах. Якщо розглянути відрізок з довжиною більшою за 1, усередині нього завжди знайдеться пара сусідніх елементів, різниця між якими не менша за середній приріст на всьому відрізку. Отже, принаймні для однієї пари сусідніх елементів \(a_i, a_{i+1}\) виконується: \[|a_{i+1} - a_i| \ge \frac{\max(l, r) - \min(l, r)}{r - l}.\] Тому завжди існуюють два сусідні елементи між якими досягається максимальна краса.
Таким чином, достатньо перебрати всі пари сусідніх елементів і знайти: \[\text{max\_beauty} = \max_{1 \le i < n} |a_{i+1} - a_i|.\]
Обчислення кількості підвідрізків з максимальною красою. Позначимо \(d_i = a_{i+1} - a_i\) — різницю між сусідніми елементами. Якщо кілька сусідніх пар мають однакове значення \(d_i\) та \(|d_i| = \text{max\_beauty}\), то вони утворюють суцільний блок із \(l\) таких різниць. Кількість підвідрізків у такому блоці обчислюється як: \[\frac{l \cdot (l + 1)}{2}.\] Тоді загальна кількість підвідрізків буде рівна сумі підвідрізків у кожному блоці.
Нехай \(dist_x\) — відстань (рівень)
вершини \(x\) від столиці (місто 1),
тобто кількість ребер на шляху від 1 до \(x\). Проведемо попередню обробку: одним DFS
з кореня 1 обчислимо \(dist_x\) для
всіх вершин та запишемо часові мітки входу/виходу
(tin/tout) для перевірки властивості
«предок/нащадок».
Розглянемо випадки для одного запиту \((u,v)\):
Якщо \(dist_u < dist_v\), то завжди вигідніше переміщатися телепортаціями вперед (переходити на рівень вниз потреби немає): за кожну телепортацію рівень збільшується на 1, отже потрібно рівно \[dist_v - dist_u\] кроків.
Інакше (\(dist_u \ge dist_v\)). Тут можливі дві стратегії:
Якщо \(v\) є предком \(u\) в дереві (тобто \(v\) лежить на шляху від \(u\) до кореня), то можна підніматися уздовж батьків до \(v\) тільки дорогою — це дає \[dist_u - dist_v\] кроків, і це оптимально, бо телепортації рухаються лише вниз від центра, а нам треба піднятися.
Якщо \(v\) не є предком \(u\), то не існує шляху, що складається тільки з підйомів до \(v\). Однак ми можемо піднятися на деяку кількість кроків (щоб опинитися на рівні \(dist_v\) або на рівні \(dist_v + 1\)), а потім використати телепортацію вниз з рівня \(dist_v\) до самого \(v\). Найпростіша й оптимальна схема: піднятися від \(u\) на \(dist_u - dist_v\) кроків до будь-якої вершини на рівні \(dist_v\), і потім двома кроками (підйом на один рівень + телепортація вниз) потрапити в \(v\). Отже отримуємо \[dist_u - dist_v + 2.\]
Отже, підсумкова формула для відповіді на запит \((u,v)\): \[\mathrm{ans}(u,v)=\begin{cases} dist_v - dist_u, & \text{якщо } dist_u < dist_v,\\[6pt] dist_u - dist_v, & \text{якщо } dist_u \ge dist_v \text{ і } v \text{ — предок } u,\\[6pt] dist_u - dist_v + 2, & \text{інакше.} \end{cases}\]
Щоб за \(O(1)\) визначати, чи є вершина \(v\) предком \(u\), під час DFS з кореня збережемо для кожної вершини моменти входу і виходу: \(tin_x\) та \(tout_x\). Тоді \[v \text{ — предок } u \quad \Longleftrightarrow \quad tin_v \le tin_u \text{ і } tout_v \ge tout_u.\]
Загальна складність розв’язку — \(O(n)\).
Оскільки Марічка може робити до \(k\) циклічних зсувів, то кожен елемент \(a_i\) у певний момент часу опиниться навпроти деякого елемента \(b_j\), де \[j = (i + t) \bmod n\] для деякого \(t \in [0, k]\).
Найвигідніше занулювати \(a_i\) тоді, коли він знаходиться навпроти мінімального можливого елемента \(b_j\) серед усіх таких положень. Тобто визначимо: \[m_i = \min_{t = 0 \ldots k} b_{(i + t) \bmod n}.\]
Тоді мінімальна загальна вартість дорівнює: \[\text{ans} = \sum_{i = 0}^{n - 1} a_i \cdot m_i.\]
Щоб ефективно знайти всі \(m_i\), потрібно обчислити мінімум на кожному вікні довжини \(k + 1\) (з урахуванням циклічності масиву). Для цього використовуємо структуру даних монотонна двостороння черга (deque):
Під час проходження елементів масиву \(b\) додаємо поточний індекс кінця вікна у чергу.
Перед додаванням видаляємо з кінця черги всі елементи, для яких \(b_{\text{новий}} \le b_{\text{останній}}\).
З початку черги видаляємо елементи, що виходять за межі поточного вікна.
Мінімум у поточному вікні завжди знаходиться на початку черги.
Таким чином, усі \(m_i\) можна знайти за \(O(n)\) часу, і загальна складність розв’язку також становить \(O(n)\).
G. Задача про нульовий підрядок
Очевидно, що елементи, які ми помістимо у вікно довжини \(m\), впливають на суму операцій, адже кожен з них треба буде занулити.
Нехай ми спершу впорядкуємо всі елементи масиву \(a\) за зростанням. Тоді \(m\) найменших елементів назвемо «хорошими», бо їх занулити дешевше, а всі інші — «поганими».
Інтуїтивно: ми хочемо, щоб у підмасиві довжини \(m\) було якомога більше хороших елементів, але можемо переставити не більше \(k\) з них. Це означає, що максимум \(k\) найменших елементів із-поза вікна можна «занести» у вікно, а натомість «викинути» \(k\) найбільших елементів, які зараз у вікні.
Для кожного вікна довжини \(m\) позначимо: \[sm = \sum_{i \in \text{вікно}} a_i\] — суму елементів у поточному вікні.
Нехай \(in\) — множина з \(k\) найбільших «поганих» елементів усередині вікна (тих, які найвигідніше замінити). Нехай \(out\) — множина з \(k\) найменших «хороших» елементів поза вікном (тих, які найвигідніше вставити).
Тоді мінімальна ціна для цього вікна дорівнює: \[\text{cost} = sm - \sum_{x \in in} x + \sum_{y \in out} y\]
тобто ми віднімаємо \(k\) найбільших значень з вікна та додаємо \(k\) найменших поза вікном, моделюючи \(k\) можливих обмінів. Відповідь до задачі — мінімальний \(cost\) з усіх вікон.
Щоб ефективно підтримувати суму \(k\) найменших елементів, використаємо техніку двох мультимножин (multiset у C++):
перша мультимножина зберігає \(k\) найменших елементів;
друга — решту елементів.
Тоді під час додавання/видалення елементу ми підтримуємо баланс, щоб перша мультимножина завжди містила рівно \(k\) найменших елементів. \(k\) найбільших можна підтримувати аналогічно, помноживши значення на -1.
Складність розв’язку — \(O(n \cdot log_n)\).