Сжатие координат, отрезков и прямоугольников. Лекция
На этой лекции разбираем одну из самых полезных техник в олимпиадном программировании — сжатие координат: зачем оно нужно, как перейти от огромных значений к компактной структуре данных и как после этого быстро отвечать на запросы. Сначала рассматриваем базовый одномерный пример с запросами суммы по диапазону значений, затем переходим к продвинутому варианту сжатия без повторных бинарных поисков, а после этого обсуждаем сжатие отрезков и прямоугольников. Отдельно разбираются технические детали реализации на C++: sort, unique, erase, lower_bound, а также инструменты для префиксных сумм вроде partial_sum, inclusive_scan и exclusive_scan. В конце лекции показывается, как идеи сжатия применяются в задачах ACMP 380 «Площадь прямоугольников» и ACMP 622 «Прямоугольное деление». Материалы: https://github.com/dmkz/competitive-programming/tree/master/mirea/cources/middle/2026/coords-compression Наш Telegram-канал: https://t.me/mireacoding Тайм-коды: 00:00:00 Введение и мотивация 00:01:45 Анонс задач на сжатие прямоугольников 00:03:40 Пример задачи на сжатие координат 00:09:40 Что такое сжатие координат 00:15:35 Ответы на вопросы 00:19:15 План решения задачи на сжатие координат 00:30:50 Продвинутое сжатие координат через указатели, без бинарного поиска 00:38:00 Продолжение ответов на вопросы 00:40:45 Детали реализации на C++: sort, unique, erase и lower_bound 00:50:40 Префикс-суммы в C++: partial_sum, inclusive_scan и exclusive_scan 00:55:30 Сжатие отрезков на числовой прямой 01:06:30 Сжатие прямоугольников на плоскости 01:07:05 Вопрос про сканирующую прямую 01:10:00 Пример использования сжатия отрезков 01:12:45 Пример использования сжатия прямоугольников 01:20:15 Задача 380. Площадь прямоугольников с сайта acmp 01:21:05 Задача 622. Прямоугольное деление с сайта acmp 01:24:50 Ответы на вопросы 01:30:10 Приёмы для удобного сжатия отрезков в C++ 01:37:12 Пример задачи на сжатие отрезков и обработку запросов 01:39:25 Завершение лекции
На этой лекции разбираем одну из самых полезных техник в олимпиадном программировании — сжатие координат: зачем оно нужно, как перейти от огромных значений к компактной структуре данных и как после этого быстро отвечать на запросы. Сначала рассматриваем базовый одномерный пример с запросами суммы по диапазону значений, затем переходим к продвинутому варианту сжатия без повторных бинарных поисков, а после этого обсуждаем сжатие отрезков и прямоугольников. Отдельно разбираются технические детали реализации на C++: sort, unique, erase, lower_bound, а также инструменты для префиксных сумм вроде partial_sum, inclusive_scan и exclusive_scan. В конце лекции показывается, как идеи сжатия применяются в задачах ACMP 380 «Площадь прямоугольников» и ACMP 622 «Прямоугольное деление». Материалы: https://github.com/dmkz/competitive-programming/tree/master/mirea/cources/middle/2026/coords-compression Наш Telegram-канал: https://t.me/mireacoding Тайм-коды: 00:00:00 Введение и мотивация 00:01:45 Анонс задач на сжатие прямоугольников 00:03:40 Пример задачи на сжатие координат 00:09:40 Что такое сжатие координат 00:15:35 Ответы на вопросы 00:19:15 План решения задачи на сжатие координат 00:30:50 Продвинутое сжатие координат через указатели, без бинарного поиска 00:38:00 Продолжение ответов на вопросы 00:40:45 Детали реализации на C++: sort, unique, erase и lower_bound 00:50:40 Префикс-суммы в C++: partial_sum, inclusive_scan и exclusive_scan 00:55:30 Сжатие отрезков на числовой прямой 01:06:30 Сжатие прямоугольников на плоскости 01:07:05 Вопрос про сканирующую прямую 01:10:00 Пример использования сжатия отрезков 01:12:45 Пример использования сжатия прямоугольников 01:20:15 Задача 380. Площадь прямоугольников с сайта acmp 01:21:05 Задача 622. Прямоугольное деление с сайта acmp 01:24:50 Ответы на вопросы 01:30:10 Приёмы для удобного сжатия отрезков в C++ 01:37:12 Пример задачи на сжатие отрезков и обработку запросов 01:39:25 Завершение лекции