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

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

В контест вошли задачи:

• Сумма на отрезке — https://judje.olprog.ru/problem/rangesum
• Количество чётных — https://judje.olprog.ru/problem/counteven
• Массовые прибавления — https://judje.olprog.ru/problem/massadd
• Массовые прибавления и точечный запрос — https://judje.olprog.ru/problem/massaddpoint
• Массовые прибавления и сумма на отрезке — https://judje.olprog.ru/problem/massaddrangesum
• Диапазон значений — https://judje.olprog.ru/problem/valuerange
• Частота значения — https://judje.olprog.ru/problem/valuefreq
• Сумма top-k элементов — https://judje.olprog.ru/problem/topksum
• Количество элементов не меньше заданного — https://judje.olprog.ru/problem/countge
• Сумма подматрицы — https://judje.olprog.ru/problem/submatrix
• Количество мод — https://judje.olprog.ru/problem/modecount
• Частоты не меньше заданного порога — https://judje.olprog.ru/problem/freqge
• Сумма на отрезке в отсортированном массиве — https://judje.olprog.ru/problem/sortedrangesum
• Суммы подотрезков — https://judje.olprog.ru/problem/subarraysums
• Подотрезки с суммой, делящейся на K — https://judje.olprog.ru/problem/subarraydivk
• Сколько раз встречалось раньше — https://judje.olprog.ru/problem/occurrencesofar

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

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

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

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

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

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

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