Два указателя для подсчёта подотрезков с суммой не больше S: как не сделать O(n^2)?
Нужно посчитать количество подотрезков массива из неотрицательных чисел, у которых сумма <= S. Наивно это O(n^2). Знаю про два указателя, но не понимаю, как через окно посчитать именно число подотрезков, а не найти один.
2 ответа
Раз все элементы неотрицательны, сумма окна монотонна по сдвигу границ — это и даёт два указателя за O(n). Идея: для каждого правого конца r найдём самый левый l, при котором сумма a[l..r] <= S. Тогда подотрезков, заканчивающихся в r и годных, ровно r - l + 1. Суммируем по всем r.
Левый указатель никогда не идёт назад: при увеличении r сумма растёт, граница l может только сдвигаться вправо. Поэтому суммарно l пройдёт массив один раз → O(n).
long long countSubarrays(const vector<long long>& a, long long S) {
long long cnt = 0, sum = 0;
int l = 0;
for (int r = 0; r < (int)a.size(); r++) {
sum += a[r];
while (sum > S) { sum -= a[l]; l++; }
cnt += (r - l + 1); // все подотрезки [l..r], [l+1..r], ..., [r..r]
}
return cnt;
}
Сложность O(n) по времени, O(1) доп. памяти. Ответ может быть до n*(n+1)/2 ≈ 5e9 для n=1e5 → обязательно long long, иначе переполнение.
Ключ к cnt += (r - l + 1): если окно [l..r] годное, то и любой его суффикс [l'..r] при l' >= l тоже годен (сумма только уменьшается). Поэтому добавляем сразу все r - l + 1 подотрезков с правым концом r.
Важное ограничение: этот трюк работает только при неотрицательных элементах — именно тогда сумма окна монотонна и левый указатель не откатывается. Если есть отрицательные числа, монотонности нет, два указателя ломаются. Тогда для «число подотрезков с суммой <= S» считай префиксные суммы pref и для каждого r нужно число l, что pref[r] - pref[l] <= S, т.е. pref[l] >= pref[r] - S — это запрос «сколько префиксов >= порога» через отсортированную структуру / дерево Фенвика по сжатым значениям, O(n log n).