Введение 0:00 Видео представляет конкурс программирования, где участники должны решить задачу по дереву сегментов и матрицам. Задача включает в себя создание декомпозиции "тяжелый свет" и построение дерева сегментов на матрицах.
Чтение входных данных 13:54 Участники должны прочитать входные данные, которые включают в себя дерево, запросы и тесты. Они также должны создать структурный тест, который представляет собой вектор из трех точек.
Решение задачи 21:03 Участники должны написать функцию, которая решает задачу, используя декомпозицию "тяжелый свет" и дерево сегментов. Они должны также создать функцию для умножения матриц и функцию для суммирования целых чисел по модулю m. В конце участники должны записать умножение матриц и подготовить решение задачи.
Создание матрицы идентификатора 33:59 Создается матрица идентификатора, которая используется для хранения информации о том, к какому пути принадлежит каждая вершина. Вершины хранятся в виде структурного пути, который включает в себя дерево сегментов, номер вершины, вектор и родительский элемент.
Разложение на тяжелые и легкие части 47:24 Вершины делятся на тяжелые и легкие, в зависимости от их размера. Для каждой вершины вычисляется ее размер и путь, на котором она находится. Вершины с размером, равным нулю, считаются листьями и хранятся отдельно.
Обновление конструктора и hld 57:46 Обновляется конструктор, который учитывает размер и вектор каждой вершины. Вершины с размером, равным нулю, считаются листьями и хранятся отдельно. Для восстановления декомпозиции тяжелого света используется dfs.
Расчет размеров поддеревьев 1:05:28 Используют функцию dfs для расчета размеров поддеревьев. Размеры поддеревьев равны количеству вершин.
Создание путей 1:10:04 Используют функцию dfs для создания путей. Векторы вершин используются для хранения информации о путях.
Создание деревьев сегментов 1:16:27 Используют функцию dfs для заполнения векторов. Создают деревья сегментов для каждого пути.
Обновление векторов и путей 1:29:58 Обновляют векторы вершин и пути при изменении значения вершины. Обновляют пути, если текущая вершина не является корнем.
Обновление матрицы 1:35:59 В видео автор объясняет, как обновить матрицу, используя информацию о текущей вершине и ее родительской вершине. Он также объясняет, как определить, где именно в матрице обновить значение, используя пути родительских вершин.
Проблемы с кодом 1:41:11 Автор обнаруживает ошибки в коде, связанные с неправильным инициализацией векторов и использованием отрицательных чисел. Он исправляет ошибки и запускает код снова, получая более корректные результаты.
Завершение работы 1:47:36 Автор завершает работу над кодом, успешно отправляя его на проверку. Он также обсуждает результаты проверки и делает вывод о том, что его код прошел проверку.
