Задачи про отрезки

Существует такой вид задач, когда нам требуется что-то посчитать на все возможных отрезках.

Задачи выглядят примерно так :

• Дан массив, найдите количество отрезков, таких что ...
• Дан массив, для каждой левой границы отрезка найти количество правых границ ИЛИ максимально правую
• Дан массив, найти минимальный или максимальный отрезок по длине

Возможен не только массив. Например, реальная задача, на которой я участвовал. Даны отрезки и диапазон $[m_1,m_2]$. Надо найти количество отрезков $[a,b]$, таких что отрезки все отрезки с номерами от $a$ до $b$ при объединение дадут отрезок по длине в диапазоне $[m_1,m_2]$. Её я разобрал здесь.

Решение в лоб

Перебрать все отрезки двумя вложенными циклами, а затем проверить фиксированный отрезок. Асимптотика данного подхода будет $O(n^2\times c)$, где $O(с)$, это асимптотика проверки отрезка, скорее всего она будет линейная, например, перебор всех элементов в отрезке и подсчёт некоторой величины.

Иногда, когда надо проверить фиксированный отрезок, величину можно считать быстрее, например, взять сумму с помощью префиксных сумм или с помощью структур данных.

Анализ задачи

Скорее всего отрезки имеют некоторые свойства :

1. При фиксированной левой границе, увеличение правой границы на один имеет свойство по которому можно посчитать результат в зависимости от предыдущего результата.

Например, сумма отрезка $[l,r+1]$ равна сумме отрезка $[l,r]$ плюс элемент $a_{r+1}$.

2. При фиксированной левой границе, увеличение правой границы, функция "подходит ли отрезок" монотонна. Скорее всего при увеличение правой границы, отрезок сначала подходит, а потом перестаёт подходить (наоборот всё тоже работает, я просто таких задач не встречал).

Например, в задаче надо найти количество отрезков, таких что gcd элементов на отрезке больше $k$. ($gcd$ наибольший общий делитель). Важное нам свойство $gcd(a,b)\le min(a,b)$, значит при увеличение правой границы отрезок сначала подходит, а потом перестаёт подходить.

3. Монотонность при передвижение левой границы. Если отрезок $[l,r]$ подходит, то отрезок $[l+1,r]$ тоже подходит. Причём это свойство без учёта монотонности по правой границе.

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

Почти всегда если выполняется 2-ое свойство то и 3-е тоже выполняется. По отдельности выполнение 3-е свойства без 2-го возможно, но если перевернуть массив, то получится монотонность по правой и 2-е свойство.

Алгоритмы

Если свойство 1 выполняется, то что-то можно сделать. TODO я особо не знаю

Если свойство 2 выполняется, то можно сделать бинпоиск по правой границе при фиксированной левой.

Если свойство 2 и 3 выполняется, то можно применить два указателя, но бинпоиск тоже работает (но всё же там уже лишний $\log$).

Иногда можно применить технику "разделяй и властвуй" или динамическое программирование.

Почти всегда бинпоиск со структурой данных с условных $O({\log }^2)$ на запрос можно заменить на спуск по дереву отрезок, что будет $O(\log )$.

Практические задачи

• Опасные группы отрезков. Разобрана.
• Перемножь последовательность!. Моя задача. TODO
• CGCDSSQ исходники в слонах