Изменения

Если <tex>t = x</tex>, то есть <tex>х </tex> - предок <tex>у </tex> в момент <tex>i</tex>-го запроса,тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.Найдем в дереве поиска наименьшего общего предка <tex>t </tex> вершин <tex>x </tex> и <tex>y </tex> на момент <tex>j</tex>-го запроса.Если <tex>t != y</tex>, тогда мы к нему обращались, и есть точка на стороне нашего прямоугольника.Если <tex>t = y</tex>, то есть <tex>y </tex> - предок <tex>x </tex> в момент <tex>j</tex>-го запроса,Значит <tex>y </tex> «всплывал», и хотя бы раз, между этими моментами выполнялся поворот вокруг ребра от <tex>у </tex> к родителю.То есть во время <tex>i</tex>-го запроса <tex>y </tex> был в поддереве <tex>х</tex>, а во время <tex>j</tex>-го запроса <tex>х </tex> в поддереве <tex>у</tex>, значит где-то между этими моментами выполнялся поворот вокруг ребра от <tex>у </tex> к родителю, и мы обращались к <tex>у</tex>, следовательно есть точка на правой стороне нашего прямоугольника

Построим из них декартово(!) дерево, где ключом будет ключ, а вспомогательным ключом – время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>х </tex> найдем минимальный <tex>у </tex> такой, что существует точка <tex>(х, у)</tex>

Приоритет <tex>y </tex> будет меняться по мере того, как мы будет симулировать работу с деревом поиска.