Бинпоиск по префиксным суммам: самый длинный подотрезок с суммой не больше S при отрицательных числах

Раз есть отрицательные — окно немонотонно, два указателя в лоб не годятся. Переходим к префиксным суммам: pref[i] = a[0] + ... + a[i-1], тогда сумма [l..r) = pref[r] - pref[l]. Условие «сумма <= S» ⇔ pref[r] - pref[l] <= S ⇔ pref[l] >= pref[r] - S. Для каждого r нужен самый левый l (l <= r), у которого pref[l] >= pref[r] - S; длина = r - l.

Если бы префиксы были отсортированы, это был бы бинпоиск. Они не отсортированы, но нам нужен минимальный индекс с условием на значение — это решается суффиксным минимумом или предподсчётом. Удобный приём: построй массив minPref[i] = минимум pref[0..i]; он неубывающий... но нужен именно индекс. Чище — обработать через структуру.

Практичный O(n log n) подход: идём по r, поддерживаем отсортированную по значению структуру встреченных (pref[l], l) и бинпоиском находим минимальный индекс среди тех, у кого pref[l] >= pref[r] - S. Чтобы «минимальный индекс», храни для каждого значения наименьший индекс и используй дерево/упорядоченный контейнер. Это аккуратно, но громоздко.

Часто проще: задача «самый длинный подотрезок суммой <= S» при произвольных знаках решается через монотонный стек префиксов + бинпоиск, либо сводится к offline-запросам. Если нужно «существует ли подотрезок суммой ровно K» — это уже хеш по префиксам за O(n). Уточни формулировку: для <= S с длиной — самый чистый путь это координатное сжатие префиксов + дерево Фенвика по минимальному индексу, O(n log n), память O(n).