Разбор задачи «Количество подотрезков с произведением меньше K»

1. Идея

Нужно посчитать количество подотрезков массива, у которых произведение элементов строго меньше K.

Полный перебор всех подотрезков слишком медленный: их O(n^2), а n может достигать 2 * 10^5.

Ключевая идея — использовать метод двух указателей, или скользящее окно.

Будем поддерживать текущий отрезок [l, r] и его произведение. Для каждого правого конца r попробуем найти минимальный l, начиная с которого произведение на отрезке [l, r] уже меньше K.

Тогда все подотрезки, которые заканчиваются в r и начинаются в позициях от l до r, подходят.

Их количество равно r - l + 1.

2. Наблюдения

Наблюдение 1. Все элементы положительны

По условию a_i >= 1. Это очень важно.

Если мы двигаем правую границу вправо, произведение не уменьшается. Если двигаем левую границу вправо, убирая элементы из окна, произведение не увеличивается.

Из-за этого окно можно корректно поддерживать двумя указателями.

Наблюдение 2. Если K <= 1, ответ всегда 0

Так как все элементы массива положительны и a_i >= 1, произведение любого непустого подотрезка тоже не меньше 1.

Но нужно, чтобы произведение было строго меньше K.

• если K = 1, нужно произведение < 1, что невозможно;
• если K < 1, тем более невозможно.

Значит, при K <= 1 сразу выводим 0.

Наблюдение 3. Для фиксированного r подходящие начала образуют непрерывный отрезок

Пусть для некоторого r найден минимальный индекс l, такой что произведение a_l * ... * a_r < K.

Тогда любой подотрезок [x, r], где x >= l, тоже подойдет, потому что мы просто убираем несколько первых положительных множителей, а значит произведение не увеличится.

Поэтому для данного r число подходящих подотрезков равно:

r - l + 1

3. Алгоритм

Будем хранить:

• l — левую границу окна,
• prod — произведение элементов на текущем окне [l, r],
• ans — общее число подходящих подотрезков.

Пусть r идет слева направо от 0 до n - 1.

Для каждого r:

1. Домножаем prod на a[r], то есть расширяем окно вправо.
2. Пока prod >= K, сдвигаем левую границу:
   • делим prod на a[l],
   • увеличиваем l.
3. После этого окно [l, r] — самое левое подходящее окно, заканчивающееся в r.
4. Добавляем к ответу r - l + 1.

4. Почему это работает

Докажем корректность.

Что поддерживает алгоритм

После завершения цикла while для текущего r выполняется:

• произведение элементов на отрезке [l, r] строго меньше K;
• если взять любой индекс левее l, то отрезок уже не подойдет.

Почему так?

• Мы добавили a[r] в окно.
• Если произведение стало слишком большим, то двигаем l вправо, пока произведение снова не станет < K.
• Как только цикл остановился, условие выполнено.
• Поскольку l увеличивался постепенно и остановился на первом возможном месте, это минимальный подходящий индекс.

Почему можно добавить r - l + 1

Рассмотрим все подотрезки, которые заканчиваются в r.

• Подотрезок [l, r] подходит.
• Любой [l+1, r], [l+2, r], ..., [r, r] тоже подходит, потому что из произведения убираются положительные множители, а значит оно не увеличивается.
• Любой подотрезок [x, r] при x < l не подходит, иначе l не был бы минимальным.

Значит, подходящих подотрезков ровно r - l + 1.

Почему алгоритм быстрый

Указатель r проходит массив один раз слева направо. Указатель l тоже только двигается вправо и за всю работу алгоритма сдвинется не более чем n раз.

То есть суммарно все действия в циклах занимают линейное время.

5. Сложность

Время

O(n)

Каждый элемент массива:

• один раз входит в окно,
• не более одного раза выходит из окна.

Память

O(n) на хранение массива.

Дополнительная рабочая память — O(1).

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long K;
    cin >> n >> K;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (K <= 1) {
        cout << 0 << '\n';
        return 0;
    }

    long long ans = 0;
    int l = 0;
    __int128 prod = 1;

    for (int r = 0; r < n; r++) {
        prod *= a[r];

        while (l <= r && prod >= K) {
            prod /= a[l];
            l++;
        }

        ans += (r - l + 1);
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n, K = map(int, input().split())
a = list(map(int, input().split()))

if K <= 1:
    print(0)
else:
    ans = 0
    l = 0
    prod = 1

    for r in range(n):
        prod *= a[r]

        while l <= r and prod >= K:
            prod //= a[l]
            l += 1

        ans += r - l + 1

    print(ans)