По-моему, просто сканирующая прямая. Разбиваем отрезок на два события - начало и конец отрезка. Сортируем события по координате. Бежим по ним, поддерживая количество открытых отрезков на данный момент. Понятно, что мы можем определить цвет отрезка от текущего события до предыдущего, исходя из четности количества открытых отрезков. И понятно, что после каждого события четность и, соответственно, цвет отрезка меняется. Поэтому задача сводится просто к пробегу по отсортированным событиям и нахождению максимального расстояния между текущим событием и предыдущим тогда, когда кол-во открытых отрезков четно. Не знаю, может я что и напутал.

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