Изменения

Задача 1 :{{Задача|definition = Есть массив <tex>a[]</tex> положительных целых чисел из <tex>n</tex> элементов и числа <tex>W >= 0</tex> и <tex>l</tex> . Требуется найти количество пар <tex>(i, j)</tex> индексов массива, таких что <tex>|j - i| <= l </tex> и <tex>\sum_{i=0}^{n - 1} [a[i]] <= W</tex>.}}Задача 2:

Задача 2:{{Задача|definition = Есть массив <tex>a[]</tex> положительных целых чисел из <tex>n</tex> элементов и числа <tex>W >= 0</tex> и <tex>l</tex> . Требуется найти количество пар <tex>(i, j)</tex> индексов массива, таких что <tex>|j - i| <= l </tex> и <tex>\sum_{i=0}^{n - 1} [a[i]] <= W</tex>.}}Для начала решим обе задачи. Вторая Первая задача решается методом [[Сортировка_слиянием|qevide&conqure (рус. разделяй и властвуй)]] - давайте разделим массив <tex>a[0...n-1]</tex> на 2 массива <tex>a[0...\frac{n}{2} - 1]</tex> и <tex>a[\frac{n}{2}...n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \frac{n}{2}, j >= \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=n/2}^{i} [a[j]]</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{n/2 + 1} [a[i]]</tex>) - для левой. Заведем два указателя (<tex>p1</tex> и <tex>p2</tex>). Изначально установим <tex>p1 = \frac{n}{2} - l + 1, p2 = \frac{n}{2}</tex>. Пока <tex>p2 - 1> \frac{n}{2}</tex> и <tex>pref[p2 ] + suf[p1] > W </tex> будем уменьшать <math>p2</math> на <math>1</math>. Если после этого <math>pref[p2] + suf[p1] <= W</math>, то к ответу прибавим <math>(p2 - \frac{n}{2} + 1) * (\frac{n}{2} - p1)</math>, посго, увеличим <math>p1</math> на <math/math>. Так будем делать, пока <math>p1 < \frac{n}{2}</math>. В конце сложим текущий ответ и ответы для половин массива - получим ответ на задачу. Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию qevide&conqure - [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков, поддерживающее 2 вида запросов : прибавление в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив <math>b[]</math>, такой что <math>b[i] = {1, если в i-м городе есть госпиталь; 0, если в i-м городе нет госпиталя}</math>.