Изменения
→Введение
Задача <math>1</math>
{{Задача
|definition = Есть массив <tex>a</tex> положительных целых чисел из <tex>n</tex> элементов. Также дано число <tex>W \geqslant 0</tex> и число <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> индексов массива, таких что <tex>|j - i| \leqslant l </tex> и <tex>\sum_sum\limits_{k=i}^{j} a_k \leqslant W</tex>.
}}
Задача <math>2</math>:
}}
Для начала решим обе задачи.
Первая задача решается методом [[Сортировка_слиянием|«разделяй и властвуй»]] {{---}} давайте разделим массив <tex>a[0 \dots n-1]</tex> на 2 массива <tex>a[0\dots\dfrac{n}{2} - 1]</tex> и <tex>a[\dfrac{n}{2} \dots n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \dfrac{n}{2}, j \geqslant \dfrac{n}{2}</tex>. Для этого воспользуемся другой известной техникой {{---}} методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_sum\limits_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных (<tex>suf[i] = \sum_sum\limits_{j=i}^{\frac{n}{2} + 1} a_j</tex>) {{---}} для левой. Заведем два указателя (<tex>p_1</tex> и <tex>p_2</tex>). Изначально установим <tex>p_1 = \dfrac{n}{2} - l + 1, p_2 = \dfrac{n}{2}</tex>. Пока <tex>p_2 - 1> \dfrac{n}{2}</tex> и
<tex>pref[p_2] + suf[p_1] > W </tex> будем уменьшать <math>p_2</math> на <math>1</math>. Если после этого <math>pref[p_2] + suf[p_1] \leqslant W</math>, то к ответу прибавим <math>(p_2 - \dfrac{n}{2} + 1) * (\dfrac{n}{2} - p_1)</math>, посго, увеличим <math>p_1</math> на <math/math>. Так будем делать, пока <math>p_1 < \dfrac{n}{2}</math>. В конце сложим текущий ответ и ответы для половин массива {{---}} получим ответ на задачу. Асимптотика такого алгоритма: <tex>T(n) = 2 * T(n / 2) + O(n) = O(n)</tex>
