Параллельный бинарный поиск по ответу на запросы оффлайн
В этом видео мы разбираем на примере задачи «K. Йошкар-Ола — Москва» с Moscow Regional Contest Qual 2025 такую технику ответов на запросы (оффлайн) как параллельный бинарный поиск по ответу, в котором все запросы обрабатываются путём одновременного сужения длины отрезка кандидатов на ответ как минимум в два раза. Запросы распределяются по веткам параллельного бинарного поиска, для каждой из которых мы продолжаем делать те же самые действия рекурсивным образом. И, наконец, рекурсивно распределив запросы в листья дерева бинарного поиска по ответу, мы сообщаем ответы на них. Воспользуйтесь тайм-кодами и скоростью х2. Исходный код выложен здесь: https://github.com/dmkz/competitive-programming/tree/master/contests/MRC-Qual-2025 Тайм-коды: 00:00:00 Начало 00:02:10 Параллельный бинарный поиск 00:09:25 Применение в задаче K. Йошкар-Ола — Москва 00:16:10 Обработка запросов в узле 00:20:50 Распределение запросов по разным веткам 00:23:08 Повтор всех этапов решения кратко 00:30:20 Разбор исходного кода на Python3 - основной его части 00:35:45 Решение на C++ 00:36:45 Структуры данных для обновления на отрезке массива 00:37:08 Корневая декомпозиция 00:41:35 Дерево отрезков 00:44:00 Дерево Фенвика 00:47:40 Прибавление на отрезке и запрос по индексу в Фенвике
В этом видео мы разбираем на примере задачи «K. Йошкар-Ола — Москва» с Moscow Regional Contest Qual 2025 такую технику ответов на запросы (оффлайн) как параллельный бинарный поиск по ответу, в котором все запросы обрабатываются путём одновременного сужения длины отрезка кандидатов на ответ как минимум в два раза. Запросы распределяются по веткам параллельного бинарного поиска, для каждой из которых мы продолжаем делать те же самые действия рекурсивным образом. И, наконец, рекурсивно распределив запросы в листья дерева бинарного поиска по ответу, мы сообщаем ответы на них. Воспользуйтесь тайм-кодами и скоростью х2. Исходный код выложен здесь: https://github.com/dmkz/competitive-programming/tree/master/contests/MRC-Qual-2025 Тайм-коды: 00:00:00 Начало 00:02:10 Параллельный бинарный поиск 00:09:25 Применение в задаче K. Йошкар-Ола — Москва 00:16:10 Обработка запросов в узле 00:20:50 Распределение запросов по разным веткам 00:23:08 Повтор всех этапов решения кратко 00:30:20 Разбор исходного кода на Python3 - основной его части 00:35:45 Решение на C++ 00:36:45 Структуры данных для обновления на отрезке массива 00:37:08 Корневая декомпозиция 00:41:35 Дерево отрезков 00:44:00 Дерево Фенвика 00:47:40 Прибавление на отрезке и запрос по индексу в Фенвике