Задачи на подотрезки: какой приём когда

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

Шесть приёмов

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

Ключевое условие: монотонность по длине

Главный вопрос, который отделяет два указателя от всего остального: если свойство выполняется для отрезка, выполняется ли оно для любого его подотрезка?

Если да — окно применимо. Сдвинули левую границу вправо, свойство сохранилось; можно двигать правую дальше.

Примеры монотонных свойств:

• сумма не больше $S$ при неотрицательных числах;
• не больше $k$ различных элементов;
• все элементы различны;
• произведение не больше $P$ при элементах не меньше единицы.

Примеры немонотонных:

• сумма не больше $S$ при наличии отрицательных — выкинув отрицательный элемент, сумму увеличиваем;
• сумма ровно $k$ — подотрезок такой суммы иметь не обязан;
• ровно $k$ различных элементов — тоже не наследуется.

Последний случай стоит запомнить отдельно: «ровно $k$» решается как «не больше $k$» минус «не больше $k-1$». Два запуска окна вместо одного невозможного.

Как читать условие

формулировка	скорее всего
«сумма на отрезке», много запросов	префиксные суммы
«самый длинный отрезок, такой что…»	два указателя
«сколько отрезков, таких что…»	два указателя или префиксы со словарём
«максимальная сумма»	Кадане
«сумма ровно $k$», есть отрицательные	префиксы со словарём
«минимум на отрезке длины $k$»	очередь с минимумом
«сумма минимумов по всем отрезкам»	стек ближайших меньших
«прибавить на отрезке» много раз	разностный массив
«максимальный прямоугольник»	стек ближайших меньших

Смена точки зрения

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

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

Формулировки, при которых стоит попробовать такую замену: «сумма по всем отрезкам», «количество отрезков, где $x$ является минимумом», «вклад каждого элемента».

Если ничего не подходит

Бывает, что задача про подотрезки не решается ни одним линейным приёмом. Тогда следующие кандидаты, по возрастанию сложности:

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

Порядок в списке не случаен: он же и порядок, в котором стоит перебирать варианты. Линейный приём почти всегда проще и надёжнее, поэтому убедиться, что он не подходит, стоит до того, как писать дерево.

Проверочный вопрос

Если решение не придумывается, задайте себе три вопроса подряд:

1. Свойство наследуется подотрезками? — окно.
2. Задача про сумму и точное значение? — префиксы и словарь.
3. Задача про минимум или максимум как функцию отрезка? — стек или очередь.

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