Структуры данных

Примеры

8 2
ABBAABCB
3 6
1 4

Дана последовательность вещественных чисел \(a_1, a_2, \dots, a_N\) и целое число \(K\). Для каждого индекса \(i\), удовлетворяющего условию \(K+1 \le i \le N-K\), рассмотрим множество его \(2K\) соседей: \[S_i = \{ a_{i-K}, \dots, a_{i-1}, a_{i+1}, \dots, a_{i+K} \}.\] Вычислим среднее арифметическое элементов этого множества: \[\mu_i = \frac{1}{2K} \sum_{x \in S_i} x\] и их стандартное отклонение: \[\sigma_i = \sqrt{ \frac{1}{2K} \sum_{x \in S_i} (x - \mu_i)^2 }.\] Элемент \(a_i\) называется выбросом, если выполняется неравенство \[|a_i - \mu_i| > 2\sigma_i.\] Если \(\sigma_i = 0\) (все числа в \(S_i\) равны), то условие превращается в \(|a_i - \mu_i| > 0\), то есть \(a_i\) считается выбросом, когда он отличается от этого общего значения.

Требуется определить количество выбросов среди всех элементов, для которых определена окрестность (т. е. для \(i = K+1, K+2, \dots, N-K\)).

Напишите и сдайте программу на языке Python, которая по заданным данным вычисляет количество выбросов.

Входные данные
Первая строка содержит два целых числа \(N\) и \(K\) (\(1 \le K \le \lfloor N/2 \rfloor\), \(N \le 200\,000\)). Вторая строка содержит \(N\) вещественных чисел \(a_1, a_2, \dots, a_N\), разделенных пробелами

Выходные данные

Выведите одно целое число — количество выбросов.
 

Примеры

В деревне Летовецк, где живут мудрые старцы и их ученики, существует древняя игра, которая называется "Летовецкая дуэль". В этой игре два игрока сражаются друг с другом, используя стопку из 10 уникальных карточек, каждая из которых имеет значение от 0 до 9. Карточки раздаются поровну: каждому игроку достаётся по 5 карточек.

Правила игры просты:

1. Игроки одновременно открывают верхнюю карточку своей стопки.

2. Тот, чья крточка старше, забирает обе вскрытые карточки и кладёт их под низ своей стопки. При этом сначала кладётся карточка первого игрока, затем карточка второго.

3. Игра продолжается до тех пор, пока у одного из игроков не закончатся карточки. Этот игрок проигрывает.

4. Особое правило: карточка со значением 0 побеждает карточку со значением 9, даже если 9 обычно старше 0.

Напишите программу, которая определяет, кто побеждает в данной игре. Вам заранее известно номера карточек первого и второго игрока! 

Для последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и целого числа \(x\) обозначим через \(f(a, x)\) количество таких целых \(i\) от \(1\) до \(n\), что \(a_i \le x\).

Для пары последовательностей целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\) обозначим через \(g(a, b, c)\) сумму значений \(|f(a, x)-f(b, x)|\) по всем целым \(x\), лежащим в отрезке \([0, c]\). Более формально, \(g(a, b, c) = \sum_{x=0}^c |f(a, x)-f(b, x)|\).

Вам даны два целых числа \(n\) и \(c\), а также две последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\), все элементы которых лежат в отрезке \([-1, c]\). Известно, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).

Скажем, что пара последовательностей целых чисел \(a_1', a_2', \ldots, a_n'\) и \(b_1', b_2', \ldots, b_n'\), все элементы которых лежат в отрезке \([0, c]\), соответствует шаблону \((a, b)\), если выполняются следующие условия:

• Для всех \(i\) (\(1 \le i \le n\)), таких, что \(a_i \ne -1\), выполняется \(a_i'=a_i\).

• Для всех \(i\) (\(1 \le i \le n\)), таких, что \(b_i \ne -1\), выполняется \(b_i'=b_i\).

• Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(a_i' \le a_{i+1}'\).

• Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(b_i' \le b_{i+1}'\).

Обозначим через \(h(a, b, c)\) сумму значений \(g(a', b', c)\) по всем парам последовательностей \((a', b')\), соответствующих шаблону \((a, b)\). Вы должны посчитать \(h(a, b, c)\). Также вы должны обработать \(q\) запросов изменения последовательностей \(a\) и \(b\) и посчитать \(h(a, b, c)\) после каждого изменения. Обратите внимание, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\), ни до всех запросов, ни после какого-либо запроса.

Формат входных данных
Первая строка содержит три целых числа \(n\), \(c\) и \(q\) (\(1 \le n \le 100\,000\), \(0 \le c \le 10^9\), \(0 \le q \le 100\,000\)) — длина последовательностей \(a\) и \(b\), ограничение на значения элементов \(a\) и \(b\) и количество запросов, соответственно.

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-1 \le a_i \le c\)) — последовательность \(a\).

Третья строка содержит \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(-1 \le b_i \le c\)) — последовательность \(b\).

В следующих \(q\) строках заданы запросы изменения. Каждый запрос задается тройкой целых чисел \(t\), \(p\), \(x\) (\(1 \le t \le 2\), \(1 \le p \le n\), \(-1 \le x \le c\)). Если \(t=1\), то данный запрос меняет \(a_p\) на \(x\). Если \(t=2\), то данный запрос меняет \(b_p\) на \(x\).

Гарантируется, что до всех изменений и после каждого изменения ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).

Формат выходных данных
Выведите \((q+1)\) строку. В \((i+1)\)-й строке (\(0 \le i \le q\)) выведите одно целое число — значение \(h(a, b, c)\) по модулю \(10^9+7\) после применения первых \(i\) запросов изменения.

Примечание
Рассмотрим первый тест из примера. В нем \(n=3\), \(c=4\), \(q=3\). До всех запросов \(a=[-1, 1, 3]\), \(b=[1, -1, 2]\). Шаблону \((a, b)\) соответствуют следующие пары последовательностей:

• \(a'=[0, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=2\).

• \(a'=[0, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=3\).

• \(a'=[1, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=1\).

• \(a'=[1, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=2\).

Таким образом, ответ на задачу до всех запросов равен \(h(a, b, 4)=2+3+1+2=8\).

В первом запросе \(t=1\), \(p=1\), \(x=2\). Этот запрос меняет \(a_1\) с \(-1\) на \(2\). Таким образом, после этого запроса \(a=[2, 1, 3]\), \(b=[1, -1, 2]\). В последовательности \(a\) нет \(-1\), поэтому в любой паре последовательностей \((a', b')\), соответствующей шаблону \((a, b)\), последовательность \(a'\) должна совпадать с \(a\). В последовательности \(a\) не выполняется условие \(a_1 \le a_2\), поэтому не существует ни одной пары последовательностей, соответствующей шаблону, а тогда \(h(a, b, 4)=0\) после первого запроса.

Для сборки лаборатории-поселения на Венеру доставлены \(n\) блоков. Блоки расположены в ряд, \(i\)-й блок имеет высоту \(h_i\).

Сборку будет осуществлять специальный робот. В процессе сборки последовательные сегменты блоков будут постепенно объединяться. При этом порядок блоков в ряду не будет меняться.

Исходно каждый блок представляет собой отдельный сегмент, сегменты пронумерованы от \(1\) до \(n\) в том же порядке, что и блоки. Если есть два соседних сегмента, составленных из блоков: сегмент из блоков \(A = [i, i+1, \ldots, i+p-1]\) и сегмент из блоков \(B = [i+p, i+p+1, \ldots, i+p+q-1]\), то после их объединения в один получается сегмент \(AB = [i, i+1, \ldots, i+p-1, i+p, i+p+1, \ldots, i+p+q-1]\).

Инструкция по сборке состоит из \(n-1\) инструкций. Каждая инструкция характеризуется одним числом, \(j\)-я инструкция характеризуется числом \(k_j\). После выполнения этой инструкции сегменты с номерами \(k_j\) и \(k_j + 1\) объединяются в один, получившийся сегмент занимает место в последовательности сегментов на месте двух объединенных сегментов, и вводится новая нумерация на сегментах в том порядке, в котором они расположены — номера сегментов, начиная с \(k_j + 2\), уменьшаются на один. После выполнения всех инструкций все сегменты окажутся объединены в один общий сегмент.

На Венере постоянно идут кислотные дожди, поэтому в процессе сборки важно для каждого сегмента блоков понимать, сколько жидкости может скопиться в этом сегменте. Пусть сегмент состоит из блоков высотой \(h_l, h_{l+1}, \ldots, h_r\). Для \(p\), где \(l \le p \le r\) определим глубину блока c высотой \(h_p\) в этом сегменте следующим образом. Посчитаем величины \(l_p = \max \{ h_l, \ldots, h_p \}\), \(r_p = \max \{ h_p, \ldots, h_r\}\). Это самые высокие блоки в сегменте слева и справа от \(p\)-го. Тогда глубина блока \(p\) в его сегменте равна \(d_p = \min(l_p, r_p) - h_p\), заметим, что \(d_p \ge 0\). Емкостью сегмента будем называть сумму глубин блоков этого сегмента, то есть \(w = d_l + d_{l+1} + \ldots + d_r\).

Задана последовательность объединений сегментов. После каждого объединения выведите емкость получившегося сегмента.

Рисунок на следующей странице показывает процесс выполнения инструкции из примера, над каждым блоком указана его глубина, а для нового сегмента показана его емкость.

Формат входных данных
Первая строка содержит одно целое число \(n\) — количество блоков (\(2 \leq n \leq 10^5\)).

Во второй строке записано \(n\) чисел \(h_1, \ldots, h_n\) (\(1 \leq h_i \leq 10^9\)).

В третьей строке записаны \(n - 1\) чисел — инструкции по объединению сегментов. Каждая инструкция характеризуется одним числом \(k_j\) (\(1 \leq k_j \leq n - j\)).

Формат выходных данных
Выведите \(n-1\) чисел — после каждого объединения сегментов выведите емкость получившегося объединенного сегмента.

Костя и Женя — создатели группы <<Бумага>> — после выпуска легендарного альбома решили создать новое музыкальное объединение <<дневные грузчики>>, для этого им нужно найти двух новых людей.

Они пригласили на кастинг \(n\) человек. Кастинг продлится \(q\) дней. В \(i\)-й из дней Костя и Женя хотят найти двух человек на отрезке с \(l_i\) по \(r_i\), которые больше всего подходят их объединению. Так как <<дневные грузчики>> занимаются современным искусством,  музыкальные навыки им не важны, и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.

Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!

Формат входных данных
В первой строке вам дано два числа \(n, q\) (\(2 \leqslant n \leqslant 4 \cdot 10^5, 1 \leqslant q \leqslant 10^6\)) — количество людей, которые пришли на кастинг, а также количество дней кастинга.

Во второй строке вам даны \(n\) чисел \(a_1, a_2, a_3, \ldots, a_n\) (\(1 \leqslant a_i \leqslant n\)) — рост каждого из кандидатов.

Также гарантируется, что все \(a_i\) различны.

В следующих \(q\) строках даны по \(2\) числа \(l_i, r_i\) (\(1 \leqslant l_i < r_i \leqslant n\)) — отрезок людей для рассмотрения в \(i\)-й день кастинга.

Формат выходных данных
Выведите \(q\) строк. В \(i\)-й строке должна быть минимальная разница роста между двумя кандидатами на отрезке в \(i\)-й день кастинга.

Примечание
В первом примере минимальная разность на отрезке \([1, 2]\) составляет \(2\) (\(3 - 1 = 2\)), на отрезке \([2, 3]\) – \(1\), на отрезке \([1, 3]\) также \(1\).

В третьем примере минимальную разность на отрезке \([4, 6]\) составляют числа \(3, 5\) (\(5 - 3 = 2\)). На отрезке \([1, 2]\) минимальную разность имеют числа \(2, 6\) (\(6 - 2 = 0\)). На отрезке \([3, 6]\) минимальную разность имеют числа \(1, 3\) (\(3 - 1 = 2\)). На отрезке \([1, 3]\) минимальную разность образуют числа \(1, 2\) (\(2 - 1 = 1\)).

Как вы знаете, девочка Даша постоянно что-то ищет. На этот раз ей дали перестановку, и она хочет найти такой её подотрезок, что ни один из элементов на его концах не является ни минимумом, ни максимумом всего подотрезка. Более формально, вас просят найти такие числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \(a_l \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_l \neq \max(a_l, a_{l + 1}, \ldots, a_r)\) и \(a_r \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_r \neq \max(a_l, a_{l + 1}, \ldots, a_r)\).

Напомнима, что перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\), выписанных в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но \(4\) присутствует в массиве, а \(2\) отсутствует).

Помогите Даше найти такой подотрезок, либо скажите, что такого подотрезка не существует.

Формат входных данных
В первой строке входных данных вам дано одно целое число \(n\) (\(1 \leqslant n \leqslant 200\,000\)) — размер перестановки.

Во второй строке входных данных вам дано \(n\) целых чисел \(a_1, a_2, \ldots a_n\) (\(1 \leqslant a_i \leqslant n\)) — элементы перестановки.

Формат выходных данных
Если искомого подотрезка не существует, выведите \(-1\).

Иначе выведите такие два числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \([a_l, a_{l + 1}, \ldots, a_r]\) удовлетворяет условиям задачи.

Если искомых подотрезков несколько, выведите любой из них.

На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из \(n\) чисел.

В частности, вы интересуетесь так называемой равномерностью массива. Предположим, что в массиве число \(b_1\) встречается \(k_1\) раз, \(b_2\) — \(k_2\) раз, и т.д. Тогда равномерностью массива называется такое минимальное целое число \(c \ge 1\), что \(c \ne k_i\) для любого \(i\).

В рамках вашего исследования вы хотите последовательно проделать \(q\) операций.

• Операция \(t_i = 1\), \(l_i\), \(r_i\) задаёт запрос исследования. Необходимо вывести равномерность массива, состоящего из элементов на позициях от \(l_i\) до \(r_i\) включительно.

• Операция \(t_i = 2\), \(p_i\), \(x_i\) задаёт запрос уточнения данных. Начиная с этого момента времени \(p_i\)-му элементу массива присваивается значения \(x_i\).

Формат входных данных
Первая строка содержит \(n\) и \(q\) (\(1 \le n, q \le 100\,000\)) — размер массива и число запросов соответственно.

Во второй строке записаны ровно \(n\) чисел — \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(1 \le a_i \le 10^9\)).

Каждая из оставшихся \(q\) строк задаёт очередной запрос.

Запрос первого типа задаётся тремя числами \(t_i = 1\), \(l_i\), \(r_i\), где \(1 \le l_i \le r_i \le n\) — границы соответствующего отрезка.

Запрос второго типа задаётся тремя числами \(t_i = 2\), \(p_i\), \(x_i\), где \(1 \le p_i \le n\) — позиция в которой нужно заменить число, а \(1 \le x_i \le 10^9\) — его новое значение

Формат выходных данных
Для каждого запроса первого типа выведите одно число — равномерность соответствующего отрезка массива.

Первый запрос состоит из ровно одного элемента — \(1\). Минимальное подходящее \(c = 2\).

Отрезок второго запроса состоит из четырёх \(2\), одной \(3\) и двух \(1\). Минимальное подходящее \(c = 3\).

Отрезок четвёртого запроса состоит из трёх \(1\), трёх \(2\) и одной \(3\). Минимальное подходящее \(c = 2\).

Бизнесмен Василий готовится к уплате налогов за квартал (три месяца). Действующая налоговая система в государстве, в котором Василий ведет свой бизнес, устроена таким образом, что величина налога зависит от прибыли в конце каждого месяца. Чистая прибыль бизнесмена определяется как разница между доходом и расходом. Разумеется, если бизнес идет не очень удачно, прибыль бизнесмена может быть отрицательной —в этом случае речь идет об убытке.

Все доходы и расходы Василий записывал в журнал в виде целых чисел. Теперь Василий должен подать налоговую декларацию с суммой доходов на конец каждого месяца, другими словами ему необходимо поделить последовательность записей в журнале на три непустые части.

При этом Василий хочет сделать это таким образом, чтобы прибыль в каждой части была одинаковой (возможно даже отрицательной) — в этом случае сумма налога будет минимальной. Менять порядок записей в журнале нельзя.

По имеющимся данным определите количество способов выполнить такое разбиение.

Входные данные

В первой строке входных данных содержится единственное целое число N — количество записей в журнале Василия (3 ≤ N ≤ 10⁵).

В следующих N строках записаны целые числа a_i, соответствующие записям в журнале (−10⁸ ≤ a_i ≤ 10⁸).

Выходные данные

Программа должна вывести единственное целое число — количество способов выполнить необходимое разбиение.

Примеры

Компания <<Flatland Dynamics>> разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из \(n\) специальных платформ, пронумерованных от \(1\) до \(n\). Расстояние между \(i\)-й и \(i+1\)-й платформой равно \(d_i\), аналогично расстояние между \(n\)-й и \(1\)-й платформой равно \(d_n\).

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом \(a\). Робот может перепрыгнуть с платформы \(i\) на платформу \(i+1\), если \(a \ge d_i\). Аналогично, прыжок с \(n\)-й платформы на \(1\)-ю возможен, если \(a \ge d_n\). При этом после каждого прыжка ловкость робота увеличивается на \(1\).

Разработчики робота выбирают одну из платформ в качестве стартовой. Они считают эксперимент удачным, если робот может, совершив \(n\) прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.

Формат входных данных
На первой строке ввода находится число \(n\) (\(3 \le n \le 10^7\)).

Вторая строка содержит одно целое число \(f\), которое описывает формат, в котором задан массив расстояний между платформами.

Если \(f = 1\), то на третьей строке находятся \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le 10^{9}\)).

Если \(f = 2\), то на третьей строке находится число \(m\) \(\left(2 \le m \le \min(n, 10^5)\right)\) и три целых числа \(x\), \(y\) и \(z\) (\(0 \le x, y, z \le 10^9\)). На четвертой строке находятся \(m\) целых чисел \(c_1, c_2, \ldots, c_m\) (\(1 \le c_i \le 10^9\)). Значения \(d_i\) вычисляются по следующим формулам.

Если \(1 \le i \le m\), то \(d_i = c_i\).

Если \(m + 1 \le i \le n\), то \(d_i = \left((x\cdot d_{i-2} + y\cdot d_{i-1} + z)\bmod 10^9\right) + 1\).

Здесь \(\bmod\) означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом <<%>>.

Формат выходных данных
Требуется вывести два целых числа: минимальную допустимую начальную ловкость \(a\) и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.

Если возможных стартовых платформ для минимальной начальной ловкости несколько, можно вывести любую из них.

Замечание
Во втором примере массив расстояний между платформами равен \([1, 2, 3, 4, 5, 18, 45, 112, 273, 662]\). Значения от \(d_6\) до \(d_{10}\) вычисляются по формулам:

\(d_6 = \left((1\cdot d_4+2\cdot d_5 + 3) \bmod 10^9\right)+1 = \left((1\cdot 4+2\cdot 5+3)\bmod 10^9\right)+1=18\)

\(d_7 = \left((1\cdot d_5+2\cdot d_6 + 3) \bmod 10^9\right)+1 = \left((1\cdot 5+2\cdot 18+3)\bmod 10^9\right)+1=45\)

\(d_8 = \left((1\cdot d_6+2\cdot d_7 + 3) \bmod 10^9\right)+1 = \left((1\cdot 18+2\cdot 45+3)\bmod 10^9\right)+1=112\)

\(d_9 = \left((1\cdot d_7+2\cdot d_8 + 3) \bmod 10^9\right)+1 = \left((1\cdot 45+2\cdot 112+3)\bmod 10^9\right)+1=273\)

\(d_{10} = \left((1\cdot d_8+2\cdot d_9 + 3) \bmod 10^9\right)+1 = \left((1\cdot 112+2\cdot 273+3)\bmod 10^9\right)+1=662\)