Комфорт Василька#500

Комфорт Василька (Editorial)

Автор: Андрій Холод

Роздробник: Павло Цікалишин

Розбір підготовано: Костянтин Денисов

Потрібно знайти найдовший підвідрізок масиву $a_{1}, \dots, a_{n}$ a_1,\dots,a_n, для якого $max (a_{l}, \dots, a_{r}) - min (a_{l}, \dots, a_{r}) \leq k$ \max(a_l,\dots,a_r) - \min(a_l,\dots,a_r) \le k. Це класична задача на два вказівники з підтримкою поточного мінімуму і максимуму в вікні.

Якщо фіксувати праву межу $r$ і збільшувати $l$ , то $max$ не зростає, а $min$ не спадає, отже різниця $max - min$ не збільшується. Тому можна рухати два вказівники: розширювати вікно вправо, а коли умова порушується — зсувати ліву межу, поки знову не стане добре.

Проблема: потрібно швидко знати $min$ і $max$ у поточному вікні $[l, r]$ [l,r]. Для цього підтримуємо std::multiset на елементах поточного вікна.

Алгоритм завжди підтримує інваріант: після внутрішнього циклу вікно $[l, r]$ [l,r] є комфортним. Для кожного $r$ ми мінімізуємо $l$ (зсуваємо його лише поки треба), тому довжина $r - l + 1$ r-l+1 є максимальною серед усіх комфортних підвідрізків, що закінчуються в $r$ . Максимум по всіх $r$ дає відповідь задачі.

Складність. Кожен індекс додається в множину рівно один раз і видаляється не більше одного разу, тому загальний час $O (n lo g n)$ O(n \log{n}), пам'ять $O (n)$ .

a_{1}, \dots, a_{n}

max (a_{l}, \dots, a_{r}) - min (a_{l}, \dots, a_{r}) \leq k

[l, r]

[l, r]

r - l + 1

O (n lo g n)