На эту неделю подготовили тренировочный контест по продвинутым префиксам и методу двух указателей.

В этой подборке собраны задачи, которые хорошо продолжают базовую тему префиксных сумм. Здесь уже встречаются не только обычные суммы на отрезках, но и XOR-префиксы, знакопеременные суммы, двумерные префиксы, разностные массивы и запросы на прямоугольниках. Вторая часть контеста посвящена методу двух указателей: окнам с ограничениями, парам в отсортированных массивах, слиянию списков и подотрезкам с заданными свойствами.

Префиксные суммы, XOR, разности и двумерные префиксы

• Сумма квадратов на отрезке — https://judje.olprog.ru/problem/sumofsquaresrange
• XOR на отрезке — https://judje.olprog.ru/problem/prefixxorrange
• Знакочередующаяся сумма на отрезке — https://judje.olprog.ru/problem/alternatingsignsum
• Сумма элементов, кратных D, на отрезке — https://judje.olprog.ru/problem/summultiplesofdrange
• Диапазонные прибавления и сумма на отрезке — https://judje.olprog.ru/problem/rangeaddrangesum
• Сумма произведений двух массивов на отрезке — https://judje.olprog.ru/problem/pointwiseproductsum
• Подсчёт особых клеток в прямоугольнике — https://judje.olprog.ru/problem/binarymatrixrectcoun
• Горячие окна K x K в тепловой карте — https://judje.olprog.ru/problem/kxkwindowsthresholdc

Два указателя и скользящее окно

• Самый длинный участок с суммой не более S — https://judje.olprog.ru/problem/longestsubarraysumle
• Количество пар с суммой K в отсортированном массиве — https://judje.olprog.ru/problem/pairssumksorted
• Слияние двух отсортированных списков — https://judje.olprog.ru/problem/mergetwosorted
• Подотрезок с суммой ровно S — https://judje.olprog.ru/problem/subarraysumexacts
• Кратчайший подотрезок с суммой не меньше S — https://judje.olprog.ru/problem/shortestsubarraysumg
• Количество подотрезков с произведением меньше K — https://judje.olprog.ru/problem/countsubarraysproduc
• Количество пар в двух отсортированных массивах с суммой K — https://judje.olprog.ru/problem/pairstwosortedsumk
• Самый длинный подотрезок с не более чем K различными значениями — https://judje.olprog.ru/problem/longestsubarrayatmos

Этот контест подойдёт тем, кто хочет:

• закрепить разные варианты префиксных сумм;
• научиться быстрее отвечать на запросы по отрезкам и прямоугольникам;
• потренировать XOR-префиксы и знакопеременные суммы;
• разобраться с разностными массивами и диапазонными обновлениями;
• уверенно применять метод двух указателей и скользящее окно;
• научиться видеть, когда отсортированность массива позволяет решить задачу за линейное время.

Во время решения задач на префиксы полезно каждый раз спрашивать себя:

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

В задачах на два указателя стоит обращать внимание на другое:

• почему границы окна можно двигать только вперёд;
• какое условие поддерживается внутри текущего окна;
• что происходит, когда сумма, произведение или число различных значений становится слишком большим;
• как аккуратно считать количество подходящих подотрезков или пар;
• как использовать отсортированность, чтобы не перебирать все варианты.

Рекомендуем решать подборку в два захода. Сначала пройти блок префиксов и убедиться, что каждая задача сводится к правильному заранее посчитанному массиву. Затем перейти к двум указателям и отдельно следить за инвариантом окна. Такой формат хорошо помогает не просто решить задачи, а научиться выбирать подходящую технику по условию.

Удачи в решении!

Ждём ваши результаты, вопросы и впечатления от задач.