Тренировочная сессия 19: минимум как точка деления отрезка СЕССИЯ

Что тренируем сегодня

На прошлой тренировке алгоритм применялся почти дословно: Дейкстра как она есть. Сегодня характер «Пика» проявляется полностью — алгоритма как такового не будет. Будет одно наблюдение, которое превращает безнадёжный перебор в несколько строк, и всё решение держится на нём.

Наблюдение такое: наименьший элемент разрезает отрезок. Всё, что торчит выше его уровня, распадается на независимые куски, между собой не соприкасающиеся. Обратная сторона того же факта — каждый элемент «владеет» ровно одним участком массива: тем, на котором он наименьший.

Обе задачи на это наблюдение, но пользуются им по-разному. В первой мы спускаемся по разрезам рекурсивно: оплачиваем уровень минимума, дробим отрезок и повторяем — приём узнаётся по характерной картинке с гистограммой или забором из столбиков разной высоты. Во второй, наоборот, никакой рекурсии нет: для каждого элемента сразу находятся границы его владения, и ответ собирается суммой вкладов за один линейный проход.

Общее у обеих задач одно, и это тоже примета «Пика»: доказательство здесь занимает больше места, чем код.

---

Теория

Минимум как точка деления отрезка. Наименьший элемент разрезает отрезок: всё, что торчит выше его уровня, распадается на независимые куски, а сам он «владеет» ровно тем участком, на котором он наименьший.

Форма 1 — рекурсивно спускаться по разрезам.

Есть отрезок столбиков разной высоты и операция, стоимость которой зависит от высоты. Находим наименьший столбик: до его уровня весь отрезок обрабатывается «одним куском», а всё, что торчит выше, распадается на независимые части — куски между позициями минимума. Каждая часть решается тем же способом, но отсчёт высоты идёт уже от уровня минимума.

Когда применять:

• дана гистограмма, забор, массив высот, и стоимость операции связана с уровнем;
• есть альтернатива «обработать по горизонтали (по уровням)» или «обработать по вертикали (по столбикам)», и надо выбрать дешёвое;
• нужна величина вида «сумма по всем подотрезкам от минимума на них» — тогда каждый элемент отвечает ровно за тот участок, где он минимален.

Как решать:

1. Найти минимум на текущем отрезке.
2. Прибавить к стоимости разницу между минимумом и уровнем, с которого мы пришли (base).
3. Разбить отрезок позициями минимума на куски и рекурсивно посчитать каждый кусок с новым уровнем base = минимум.
4. Сравнить полученную стоимость с «вертикальной» альтернативой — обработать каждый столбик отрезка отдельно, то есть длина отрезка, — и взять меньшее.

Мини-пример. Высоты 3 1 3. Минимум равен 1, платим 1 за весь отрезок. Остаются два куска — 3 слева и 3 справа, у каждого уровень отсчёта 1, стоимость $3 - 1 = 2$, но вертикальная альтернатива для куска из одного столбика равна 1 — берём 1. Итого $1 + 1 + 1 = 3$, и вертикальная альтернатива для всего отрезка тоже 3. Ответ 3.

Пункт 4 — не украшение: без сравнения с вертикальным вариантом решение неверно. Ровно поэтому «покрасить всё горизонтально» — не жадность, а только одна из двух веток.

Где ошибаются в узнавании: делят отрезок пополам, как в обычном «разделяй и властвуй». Здесь точка деления не середина, а минимум, и именно это делает куски независимыми — над уровнем минимума они не соприкасаются.

Сложность приёма: в лоб $O(n^2)$ в худшем случае (отсортированный массив), чего хватает при $n$ до нескольких тысяч; с разреженной таблицей минимумов или стеком — до $O(n\log n)$.

Каркас приёма:

Форма 2 — сразу найти границы владения. У того же наблюдения есть вторая сторона. Вместо того чтобы спускаться по разрезам, можно для каждого элемента сразу спросить: на каком максимальном отрезке он наименьший? Ответ задаётся двумя ближайшими соседями, которые его превосходят, — слева и справа. Всё, что между ними, элемент «держит» единолично.

Когда полезна именно эта форма:

• нужна сумма (или количество) по всем подотрезкам, а не ответ для одного отрезка целиком;
• размер входа такой, что даже $O(n\log n)$ впритык — границы владения находятся за чистую линию;
• вклад элемента выражается формулой от длин двух «плеч» его отрезка.

Как искать границы за линию — монотонным стеком. Идём слева направо и держим в стеке позиции, значения в которых монотонны. Приходит новый элемент: выталкиваем из стека всех, кого он «перебивает», — они уже никогда не станут ничьей границей, потому что новый элемент закрывает их собой. То, что осталось на вершине, и есть ближайший превосходящий сосед. Каждая позиция кладётся в стек один раз и снимается один раз, отсюда линейность.

Мини-пример: массив 2 1 3. Для единицы в середине превосходящих соседей нет ни слева, ни справа, значит она владеет всем массивом — тремя позициями, и подотрезков, где она минимум, четыре: $(1 - (-1)) \cdot (3 - 1) = 4$. Двойка слева владеет только собой, тройка справа — тоже.

Важная тонкость — равные значения. Если рядом стоят одинаковые числа, отрезок, содержащий их обоих, попадёт во владение к каждому, и вклад посчитается дважды. Лечится асимметрией: с одной стороны граница ищется строго, с другой — нестрого. Тогда среди равных владельцем становится ровно один. Правило легко запомнить как «строго с одной стороны, нестрого с другой», а проверяется оно мгновенно на массиве из одинаковых чисел.

Где приём перестаёт работать. Обе формы опираются на то, что элементы сравнимы и минимум действительно разрезает отрезок. Если стоимость зависит не от минимума, а, скажем, от суммы или от количества различных значений, разрезание не даёт независимости кусков, и приём не применим. Вторая граница — необходимость знать не только минимум, но и его позицию: если задача про мультимножество и порядок не важен, всё решается сортировкой, и никакие разрезы не нужны.

С чем путают. Обычное «разделяй и властвуй» делит отрезок пополам и склеивает ответы; здесь точка деления не середина, а минимум, и именно поэтому куски получаются независимыми. Второй сосед — дерево отрезков: оно тоже умеет отвечать про минимум на отрезке, но это структура для запросов, а сегодня запросов нет — есть одна статическая задача, и заводить структуру ради неё избыточно.

Сложность приёма: рекурсия по разрезам — от $O(n\log n)$ до $O(n^2)$ в худшем случае, в зависимости от того, как ищется минимум; подсчёт владений монотонным стеком — всегда $O(n)$.

---

Задача 1 — CF ~1900 — «Painting Fence»

Что дано

Забор состоит из n вертикальных досок шириной 1; i-я доска имеет высоту a[i]. Доски стоят подряд, впритык.

Есть кисть шириной ровно 1. Одним движением можно провести горизонтальный или вертикальный мазок: кисть движется по прямой и не должна выходить за пределы забора — то есть весь мазок обязан идти по крашеной площади. Нужно найти минимальное число движений, чтобы покрасить весь забор.

Формат ввода:

• Строка 1: число n ($1 \le n \le 5000$).
• Строка 2: n чисел a[1] … a[n] ($1 \le a_i \le 10^9$).

Формат вывода: одно число — минимальное количество мазков.

Пример 1:

Ввод:
5
2 2 1 2 1

Вывод:
3

Пример 2:

Ввод:
2
2 2

Вывод:
2

Пример 3:

Ввод:
1
5

Вывод:
1

Разберём на примере

Первый пример: высоты 2 2 1 2 1. Нарисуем забор по слоям снизу вверх.

Горизонтальные мазки красят непрерывный кусок одного уровня целиком. Значит на первом уровне достаточно одного мазка, на втором нужно два — итого три. Вертикально было бы пять мазков (по одному на доску). Ответ 3, совпадает с ожидаемым.

Теперь то же самое, но так, как это делает рекурсия. Минимум по всему забору равен 1 — платим один горизонтальный мазок и «срезаем» нижний слой. Над ним забор распадается на куски там, где стояли доски высоты 1, — то есть на [2, 2] (доски 1–2) и [2] (доска 4), и в каждом куске высоты теперь отсчитываются от уровня 1.

• Кусок [2, 2] с уровнем отсчёта 1: минимум 2, платим $2 - 1 = 1$ мазок, выше ничего не остаётся. Итого 1. Вертикальная альтернатива — 2 мазка. Берём 1.
• Кусок [2] с уровнем отсчёта 1: платим $2 - 1 = 1$. Вертикальная альтернатива — тоже 1. Берём 1.

Складываем: $1 + 1 + 1 = 3$. Вертикальная альтернатива для всего забора — 5. Ответ 3.

Второй пример показывает, зачем вообще нужна вертикальная альтернатива... а вот и не показывает: 2 2 даёт горизонтально $2$ мазка и вертикально тоже $2$. Настоящий контрпример — третий пример: одна доска высоты 5. Горизонтально это 5 мазков, вертикально — один. Если бы решение всегда красило по слоям, оно ответило бы 5 вместо 1.

И ещё важное наблюдение из третьего примера: сравнивать с вертикальным вариантом нужно на каждом уровне рекурсии, а не один раз в конце. Забор 1 5 1 5 1 выгодно резать по нижнему слою, а вот получившиеся куски [5] и [5] — красить вертикально.

Идея решения

Алгоритм в одну фразу: для отрезка досок с уровнем отсчёта base взять минимум m, заплатить m − base горизонтальных мазков, рекурсивно посчитать куски между позициями минимума с новым уровнем m и вернуть минимум из полученной суммы и длины отрезка (вертикальный вариант).

Почему горизонтальных мазков на слой ровно столько, сколько кусков. Мазок обязан идти по забору не прерываясь. Значит один мазок красит ровно один непрерывный кусок одного уровня — ни больше, ни меньше. Отсюда «стоимость слоя = число кусков на нём».

Почему куски независимы. Все доски отрезка имеют высоту не ниже m, поэтому уровни от base до m покрываются полосами на весь отрезок — по одному мазку на уровень, всего m − base. Выше уровня m доски высоты ровно m исчезают, и оставшиеся группы досок разделены пустотой: ни один горизонтальный мазок не может пройти из одной группы в другую. Значит их можно красить независимо и просто складывать стоимости.

Почему нужен min с длиной отрезка. Вместо всей описанной конструкции отрезок всегда можно закрасить вертикально — по одному мазку на доску. Это r − l + 1 мазков, и иногда это дешевле: пример 3. Любое оптимальное решение либо использует хотя бы один горизонтальный мазок на самом нижнем свободном уровне отрезка (и тогда, раз мазок идёт по всему уровню и уровни ниже m тоже надо покрыть, выгодно закрыть все m − base уровней полосами), либо не использует горизонтальных мазков вовсе — и тогда это чистая вертикаль. Обе ветки мы и сравниваем.

Почему хватает $O(n^2)$. При n до 5000 худший случай — отсортированный массив, где каждый уровень отрезает по одной доске: суммарно около $n^2/2 \approx 1.25 \cdot 10^7$ просмотров. Это проходит.

Псевдокод

рекурсия(l, r, base):
    если l > r: вернуть 0
    ширина = r - l + 1                     // вертикальная альтернатива
    m = минимум a[l..r]
    стоимость = m - base                   // горизонтальные полосы до уровня m
    i = l
    пока i <= r и стоимость < ширина:
        k = ближайшая позиция минимума начиная с i (или r+1, если её нет)
        если k > i:
            стоимость += рекурсия(i, k-1, m)   // кусок между позициями минимума
        i = k + 1
    вернуть min(стоимость, ширина)

вывести рекурсия(0, n-1, 0)

Код решения

Комментарии по реализации. Условие cost < width в заголовке цикла — не просто оптимизация, а то, что удерживает решение в пределах времени: как только накопленная стоимость догнала вертикальную альтернативу, дальше считать бессмысленно, ответ уже известен. В Python поиск минимума и поиск ближайшей позиции сделаны встроенными min и list.index вместо явных циклов: на худшем входе (строго возрастающие высоты, глубина рекурсии 5000) явные циклы по элементам дают заметно больше времени, а встроенные функции выполняют тот же просмотр внутри интерпретатора. И обязательно поднимите лимит рекурсии: на возрастающем заборе глубина равна n, а стандартный лимит Python — тысяча. Переполнения нет: cost начинается с m − base (до $10^9$), но в этом случае сразу же оказывается больше ширины, и цикл не выполняется ни разу.

Проверка на примерах

Пример 1: 2 2 1 2 1. Разбор выше даёт $1 + 1 + 1 = 3$ против вертикальных 5. Наш вывод: 3 — совпадает с ожидаемым.

Пример 2: 2 2. Минимум 2, стоимость $2 - 0 = 2$, выше уровня 2 досок не осталось, кусков нет. Ширина тоже 2, берём 2. Наш вывод: 2 — совпадает.

Пример 3: 5. Минимум 5, стоимость 5, ширина 1. Условие cost < width ложно с самого начала — возвращаем ширину, то есть 1. Наш вывод: 1 — совпадает.

Прогоним ещё несколько самостоятельно построенных случаев — в них проверяются ветки, которых в примерах условия нет:

Решение выдаёт на них 2, 4, 5, 1 и 3 соответственно.

Крайние случаи

• n = 1. Ответ 1 при любой высоте: вертикаль всегда выигрывает у высоты больше единицы.
• Все доски одной высоты h. Ответ $\min(h, n)$ — либо h полос, либо n вертикальных мазков.
• Строго возрастающие высоты. Худший случай по времени: глубина рекурсии равна n. Здесь же проверяется поднятый лимит рекурсии в Python.
• Высота до $10^9$ при n = 1. Начальная стоимость огромна, но сразу отсекается сравнением с шириной — и переполнения не возникает.
• Забор-«гребёнка» 1 9 1 9 1. Нижний слой один мазок, дальше каждая высокая доска красится вертикально.
• Все доски высоты 1. Один горизонтальный мазок на всё — ответ 1.

Типичные ошибки

1. Всегда красить по слоям. На одной доске высоты $10^9$ такое решение ответит $10^9$ вместо 1.
2. Сравнивать с вертикалью только на верхнем уровне. Сравнение обязано быть внутри рекурсии: выгодность вертикали возникает у отдельных кусков, а не у забора целиком.
3. Делить отрезок пополам. Куски независимы именно потому, что разделены позициями минимума; деление посередине этого свойства не даёт.
4. Забыть про уровень отсчёта base. Без него нижние слои оплачиваются повторно в каждом куске.
5. Рекурсия без поднятого лимита в Python. Возрастающий забор из 5000 досок — глубина 5000.
6. Считать позиции минимума заранее один раз. Позиции минимума нужны для текущего отрезка, а не для всего массива: у каждого куска свой минимум.
7. Пропустить отсечение по ширине. Без него худший случай в Python не укладывается по времени, хотя ответ остаётся правильным.

Сложность

Время: $O(n^2)$ в худшем случае, $O(n\log n)$ на «сбалансированных» входах. Память: $O(n)$ на массив плюс глубина рекурсии.

---

Задача 2 — CF ~1900 — «Imbalanced Array»

Что дано

Дан массив из n чисел. Несбалансированностью подотрезка называется разность между его максимумом и минимумом. Несбалансированность всего массива — это сумма несбалансированностей всех его подотрезков. Нужно её посчитать.

Формат ввода:

• Строка 1: целое n ($1 \le n \le 10^6$).
• Строка 2: n целых чисел a[1] … a[n] ($1 \le a_i \le 10^6$).

Формат вывода: одно число — несбалансированность массива.

Пример 1:

Ввод:
3
1 4 1

Вывод:
9

В этом примере шесть подотрезков: [1], [1,4], [1,4,1], [4], [4,1], [1]. Их несбалансированности — 0, 3, 3, 0, 3, 0; в сумме 9.

Разберём на примере

Подотрезков у массива длины n примерно $n^2/2$, а n доходит до миллиона — значит перебрать их нельзя даже теоретически. Придётся считать сумму, ни разу не взглянув на отдельный подотрезок.

Первый шаг — разорвать разность. Сумма по всем подотрезкам разности «максимум минус минимум» равна сумме всех максимумов минус сумма всех минимумов:

$\sum_{\text{отрезки}} (\max - \min) \;=\; \sum_{\text{отрезки}} \max \;-\; \sum_{\text{отрезки}} \min$

Это уже большое облегчение: две одинаковые по устройству задачи вместо одной сложной. Дальше разберём только сумму максимумов — для минимумов всё зеркально.

Второй шаг — поменять порядок суммирования. Вместо «для каждого отрезка найти его максимум» спросим наоборот: для каждого элемента — на скольких отрезках максимум это он. Тогда сумма максимумов равна сумме по элементам «значение, умноженное на количество отрезков, где элемент главный».

Посмотрим на пример 1 4 1 (нумерация с нуля).

• Элемент 4 в позиции 1 больше обоих соседей, поэтому он максимум на любом отрезке, который его содержит: слева границу можно взять двумя способами (начать в позиции 0 или 1), справа тоже двумя (кончить в 1 или 2). Итого $2 \cdot 2 = 4$ отрезка.
• Элемент 1 в позиции 0 — максимум только на отрезке из себя одного: стоит захватить позицию 1, и максимумом станет четвёрка. Один отрезок.
• Элемент 1 в позиции 2 — аналогично, один отрезок.

Сумма максимумов: $4 \cdot 4 + 1 \cdot 1 + 1 \cdot 1 = 18$. Сумма минимумов считается тем же способом: единица в позиции 0 — минимум на отрезках [0,0], [0,1], [0,2], четвёрка — только на [1,1], единица в позиции 2 — на [1,2] и [2,2]. Итого $1 \cdot 3 + 4 \cdot 1 + 1 \cdot 2 = 9$. Ответ: $18 - 9 = 9$ — сходится.

Третий шаг — понять, как считать «сколько отрезков» быстро. Элемент в позиции i является максимумом ровно на тех отрезках, которые содержат i и не содержат ничего большего. Значит границы задаются ближайшими «сильными» соседями: пусть L — ближайшая слева позиция со значением больше a[i], а R — ближайшая справа. Тогда левый конец отрезка можно выбрать любым из позиций от L + 1 до i, а правый — от i до R − 1, то есть количество отрезков равно $(i - L)(R - i)$.

Это и есть отрезок владения: кусок массива, на котором элемент главный. Заметьте связь с первой задачей: там мы рекурсивно делили отрезок в точке минимума, и каждый кусок оказывался ровно тем, чем минимум «владеет». Здесь та же геометрия, только границы владения ищутся напрямую.

Идея решения

Алгоритм в одну фразу: посчитать для каждого элемента, на скольких подотрезках он является максимумом, и на скольких — минимумом; ответ равен сумме значение × (число отрезков-максимумов − число отрезков-минимумов).

Как найти границы владения за линию. Для каждой позиции нужен ближайший слева элемент, который «сильнее». Наивно это квадрат, но здесь работает монотонный стек: идём слева направо и держим в стеке позиции, значения которых убывают. Приходит новый элемент — выталкиваем из стека всех, кто его не превосходит (они уже никогда не станут ничьей левой границей: новый элемент их закрывает), и тогда на вершине стека остаётся ровно искомый ближайший «сильный» сосед. Каждая позиция попадает в стек один раз и выталкивается один раз, поэтому весь проход линеен.

Тонкость с равными значениями. Если в массиве есть одинаковые числа, отрезок, где их несколько, посчитается несколько раз — по разу за каждый из равных максимумов. Лечится это асимметрией сравнений: с одной стороны граница ищется по строгому неравенству, с другой — по нестрогому. Тогда среди равных «владельцем» становится ровно один — например, самый левый, — и двойного счёта не возникает. Правило простое: строго с одной стороны, нестрого с другой; какую именно сторону сделать строгой, неважно, важно не сделать обе одинаковыми.

Проверить это стоит на массиве из одинаковых чисел, скажем 2 2 2. Отрезков ровно шесть, максимум на каждом равен двум, значит сумма максимумов обязана быть 12. При правильной асимметрии владения распределяются так: первый элемент владеет тремя отрезками, второй двумя, третий одним — всего шесть, и сумма $2 \cdot 6 = 12$. Если же обе границы искать строго, каждый элемент будет владеть только собой, отрезков насчитается три, а сумма получится 6 — ровно вдвое меньше нужного.

Почему это тот же приём, что и в первой задаче. Обе задачи опираются на одно свойство: минимум (или максимум) разрезает отрезок, и каждый элемент отвечает ровно за тот кусок, где он главный. Различается только способ этим воспользоваться: рекурсивно спускаться по разрезам, как в первой задаче, или сразу найти границы владения для всех элементов и сложить вклады, как здесь. Второй способ линеен и потому годится для миллиона элементов; первый нагляднее и удобнее, когда стоимость зависит от уровня, а не от количества.

Псевдокод

прочитать n и массив a

функция сумма_владений(главный_это_максимум):
    // левая граница: ближайшая позиция со «строго сильнее»
    стек = пустой
    для i от 0 до n-1:
        пока стек не пуст и вершина слабее a[i] (строго):
            снять вершину
        left[i] = вершина стека или -1
        положить i в стек

    // правая граница: ближайшая позиция «не слабее» (нестрого)
    стек = пустой
    итог = 0
    для i от n-1 вниз до 0:
        пока стек не пуст и вершина не сильнее a[i] (нестрого):
            снять вершину
        right = вершина стека или n
        положить i в стек
        итог += a[i] * (i - left[i]) * (right - i)
    вернуть итог

вывести сумма_владений(максимум) - сумма_владений(минимум)

Код решения

Комментарии по реализации. Ответ растёт как $O(n^2 \cdot \max a)$ — при миллионе элементов это порядка $10^{17}$, поэтому накопитель обязан быть 64-битным, а произведение (i - left) * (right - i) нужно приводить к 64 битам до умножения, а не после. Одна функция с флагом вместо двух почти одинаковых — не только экономия: два скопированных куска с четырьмя сравнениями, которые надо развернуть в противоположную сторону, почти гарантированно разъедутся при правке. При $n = 10^6$ важен и ввод: построчное чтение в Python здесь безнадёжно, нужен один read().split(). Проверено на предельном тесте: C++ укладывается примерно в 0,2 секунды, Python — примерно в 1,7, то есть у Python запас невелик, но он есть.

Проверка на примерах

Пример 1: массив 1 4 1.

Сумма максимумов:

Итого 18.

Сумма минимумов:

Итого 9. Ответ: $18 - 9 = 9$ — совпадает с эталоном.

Обратите внимание на строку с позицией 2 в таблице минимумов: её левая граница равна нулю, хотя в позиции 0 стоит такая же единица, а не меньшее число. Это и есть асимметрия сравнений в действии — при равенстве владельцем отрезка назначается левый из равных. Если бы левая граница искалась нестрого (то есть равные тоже выталкивались бы), позиция 2 получила бы границу −1, владела бы тремя отрезками вместо двух, и отрезок [0, 2] оказался бы засчитан дважды: сумма минимумов стала бы 10, а ответ — неверные 8.

Крайние случаи

• n = 1. Единственный подотрезок, его несбалансированность 0. Формула даёт то же: элемент владеет одним отрезком и как максимум, и как минимум, вклады сокращаются.
• Все элементы равны. Ответ 0: суммы максимумов и минимумов совпадают. Это и есть главный тест на правильную асимметрию — при ошибке он выдаёт не ноль.
• Строго возрастающий массив. Каждый элемент — максимум на отрезках, начинающихся где угодно слева и кончающихся на нём самом, и минимум на отрезках, начинающихся на нём. Полезно прогнать руками 1 2 3 и сверить с ответом 4.
• Строго убывающий массив. Зеркальная проверка, ловит перепутанные направления обходов.
• Максимальные значения ($a_i = 10^6$, $n = 10^6$). Проверка на переполнение: ответ порядка $10^{17}$.
• Массив вида 1 10^6 1 10^6 …. Стек постоянно то растёт, то опустошается — хороший тест на то, что счётчик не сбивается.

Типичные ошибки

1. Симметричные сравнения с обеих сторон. При равных элементах отрезок либо считается дважды, либо не считается вовсе. Проверяется мгновенно на массиве из одинаковых чисел: ответ обязан быть нулём.
2. Переполнение при умножении. (i - left) * (right - i) в 32-битном типе рвётся уже при $n$ порядка $10^5$; приводить к 64 битам надо до умножения.
3. Считать сумму максимумов и минимумов за один проход с общим стеком. Стеки монотонны в разные стороны, объединить их не выйдет — это два независимых прохода.
4. Искать границы бинарным поиском по разреженной таблице. Работает и даёт $O(n\log n)$, но на миллионе элементов памяти под таблицу уйдёт больше, чем нужно, а стек даёт линию.
5. Перебирать подотрезки хотя бы для маленьких n, а дальше «оптимизировать». Соблазн проверить формулу перебором полезен для отладки, но в сдаваемом решении квадратичной ветки быть не должно.
6. Медленный ввод. Миллион чисел через построчное чтение в Python — сразу превышение лимита времени, независимо от алгоритма.

Сложность

Время: $O(n)$ — четыре линейных прохода со стеком (два на максимумы, два на минимумы), каждая позиция попадает в стек и покидает его по одному разу. Память: $O(n)$ — массив, стек и массив левых границ.

---

Самостоятельная тренировка

Все четыре — на сегодняшнее наблюдение: в каждой нужно понять, каким участком «владеет» элемент, оказавшийся на нём главным.

• Codeforces 1691D «Max GEQ Sum» (~CF 1800) — нужно проверить, что для каждого подотрезка его максимум не меньше суммы элементов. Подсказка: перебирать подотрезки не нужно — достаточно для каждого элемента рассмотреть тот участок, где он максимум, и проверить условие только на нём; сумма на подотрезке при этом ищется через префиксные суммы и их минимумы-максимумы.
• Codeforces 547B «Mike and Feet» (~CF 1900) — для каждого размера окна от 1 до n нужно найти максимальный среди минимумов по всем окнам этого размера. Прямое применение владения: элемент отвечает за все окна длиной до размера своего участка, и остаётся аккуратно «протащить» ответы от больших длин к меньшим.
• Codeforces 1313C2 «Skyscrapers (hard version)» (~CF 1900) — высоты нужно уменьшить так, чтобы профиль не имел «ямы» (не рос после падения), максимизировав сумму. Подсказка: зафиксируйте вершину профиля и посчитайте лучшие суммы слева и справа монотонным стеком — в обоих проходах участок владения элемента и подсказывает переход.
• Codeforces 1156E «Special Segments of Permutation» (~CF 2200) — в перестановке нужно посчитать отрезки, у которых максимум равен сумме элементов на концах. Самая сложная в наборе: здесь владение максимума комбинируется с приёмом «перебирать всегда меньшую половину», и именно это даёт итоговую сложность.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

Сегодня обе задачи решались одним наблюдением, взятым с двух сторон: минимум разрезает отрезок — значит каждый элемент владеет своим участком. Первая задача спускалась по разрезам рекурсивно, вторая сразу считала границы владения стеком. Если сейчас кажется, что «идею надо было просто знать», — отчасти так и есть, и именно поэтому мы разбираем приёмы отдельно от задач: узнавание тренируется списком признаков в условии, а не количеством решённых задач.

На следующей тренировке — бинарный поиск по ответу, но в варианте, где проверка кандидата не сводится к пробегу по массиву: объекты придётся сжать в битовые маски, и вся сложность будет прятаться именно в проверке.