Випуклий масив#11812

Випуклий масив (Розбір)

Автор задачі:	Антон Тригуб
Задачу підготував:	Василь Меренич
Розбір написав:	Костянтин Денисов

Твердження 1. У випуклого масиву різниці між сусідніми елементами не зменшуються. Тобто, якщо позначити $d_{i} = b_{i + 1} - b_{i}$ d_i = b_{i+1} - b_i, то для кожного $i$ виконується нерівність $d_{i} \leq d_{i + 1}$ d_i \le d_{i+1}.

Це безпосередньо випливає з визначення випуклості.

Оскільки послідовність різниць $d_{i} = b_{i + 1} - b_{i}$ d_i = b_{i+1} - b_i є неспадною, існує такий індекс $k$ , що $d_{i} \leq 0$ d_i \le 0 для $i < k$ i < k і $d_{i} \geq 0$ d_i \geq 0 для $i \geq k$ i \geq k. Це означає, що масив можна розбити на дві монотонні випуклі послідовності: спадну $b_{1}, \dots, b_{k}$ b_1, \dots, b_k і зростаючу $b_{k}, \dots, b_{n}$ b_k, \dots, b_n.

Тоді потрібно розбити масив на дві зростаючі випуклі послідовності, які перетинаються у найменшому елементі масиву.

Логічно будувати ці послідовності, додаючи елементи у порядку зростання. Але як визначити, до якої з них приєднати новий елемент?

Для цього достатньо зберігати по два останні елементи кожної з послідовностей. Це дозволить перевіряти умови випуклості та правильно розподіляти нові елементи.

Тоді можна написати динаміку $d p [i] [a] [b] [c]$ dp[i][a][b][c] ( $i > a$ i > a, $i > b > c$ i > b > c), яка буде приймати значення true або false і позначати, чи можемо розділити перші $i$ чисел на дві послідовності. Перша послідовність закінчується на елементах з індексами $i, a$ , а друга — на $b, c$ . Тоді маємо рішення за $O (n^{4})$ \mathcal{O}(n^4).

Звернемо увагу, що в досяжних станах рівно одне з $a, b, c$ a, b, c буде рівне $i - 1$ i-1. Тому насправді можна оптимізувати попередню динаміку до $O (n^{3})$ \mathcal{O}(n^3).

Крім того, замість бінарних значень true та false для трійки $i, a, b$ i, a, b можна зберігати найбільше можливе значення $c$ , оскільки вигідно мінімізувати різницю між $b$ та $c$ . І таким чином матимемо рішення за $O (n^{2})$ \mathcal{O}(n^2).

Для того, щоб оптимізувати розв'язок, потрібно ще глибше зануритися в особливості станів. Зокрема, ми вже розглянули, що індекс $i - 1$ i-1 є важливим у станах. Тепер розглянемо також індекс $i - 2$ i-2.

Є три випадки станів $i, a, b, c$ i, a, b, c:

$i, i - 1, b, c$ i, i - 1, b, c;
$i, i - 2, i - 1, c$ i, i - 2, i - 1, c;
$i, c, i - 1, i - 2$ i, c, i - 1, i - 2;

Для другого і третього випадку достатньо зберегти лише максимальні можливі досяжні значення $c$ для фіксованого $i$ . Аналогічно маємо для першого випадку для фіксованого $i$ та $b$ , але тут більше параметрів, тому цей випадок є складнішим.

Розглянемо переходи для фіксованого $i$ . Маємо не більше одного стану другого та третього типів. Станів першого типу може бути багато, тому розглянемо їх окремо, щоб оптимізувати переходи з цих станів.

Розглядаємо стан $i, i - 1, b, c$ i, i-1, b, c. Розглянемо два випадки залежно від того, в яку послідовність ставимо елемент $i + 1$ i+1:

Додаємо в першу підпослідовність. Тоді має виконуватись умова: $a_{i + 1} + a_{i - 1} \geq 2 \cdot a_{i}$ a_{i+1} + a_{i-1} \geq 2 \cdot a_i. І переходимо в стан: $i + 1, i, c, d$ i + 1, i, c, d. Помітимо, що в цьому стані перехід відбувається незалежно від значень $c, d$ , і перехід відбувається зі стану першого типу до стану першого типу.
Тобто якщо для фіксованого $i$ зберігати всі можливі стани як множину пар $(c, d)$ , то при переході до наступного стану $i + 1$ i+1 всі ці стани залишаться в такому ж вигляді, якщо умова $a_{i + 1} + a_{i - 1} \geq 2 \cdot a_{i}$ a_{i+1} + a_{i-1} \geq 2 \cdot a_i виконується.
Додаємо в другу підпослідовність. Тоді має виконуватись умова: $d + a_{i + 1} \geq 2 \cdot c$ d + a_{i+1} \geq 2 \cdot c, що еквівалентно $a_{i + 1} \geq 2 \cdot c - d$ a_{i+1} \geq 2 \cdot c - d. І переходимо в стан: $i + 1, c, i, i - 1$ i+1, c, i, i-1, тобто у стан третього типу.
Для станів третього типу потрібно максимізувати $c$ , тому необхідно знайти максимальне $c$ серед усіх станів, що задовольняють умову $a_{i + 1} \geq 2 \cdot c - d$ a_{i+1} \geq 2 \cdot c - d.

Переходи зі станів другого і третього типу оптимізувати не треба, бо їх не більше одного.

Тепер залишилося оптимізувати переходи зі станів першого типу до третього. Для цього можна відсортувати стани $(c, d)$ за значенням $2 \cdot c - d$ 2 \cdot c - d. Після цього для кожного нового елемента $a_{i + 1}$ a_{i+1} потрібно знаходити максимальне значення $c$ серед тих станів, де $2 \cdot c - d \leq a_{i + 1}$ 2 \cdot c - d \le a_{i+1}.

Щоб ефективно знаходити цей максимум, немає необхідності використовувати складні структури даних, такі як дерево відрізків або дерево Фенвіка. Достатньо std::set, якщо помітити, що стани, для яких існує інший стан з меншим $2 \cdot c - d$ 2 \cdot c - d і водночас більшим $c$ , не потрібно зберігати.

Таким чином, якщо відсіяти невигідні стани, то отримані стани будуть відсортовані як за $2 \cdot c - d$ 2 \cdot c - d, так і за $c$ . Тоді для знаходження максимуму на префіксі достатньо одного виклику lower_bound.

Фінальна складність рішення: $O (n lo g n)$ \mathcal{O}(n \log{n}).