Изменения

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

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

У нас есть вершина <tex>хx</tex>, у которой есть правый сын <tex>уy</tex>, и приоритет <tex>хx</tex> больше чем у <tex>уy</tex>, их надо поменять, то есть дотронуться до вершины <tex>уy</tex>, чего мы делать не хотели в этой строке.Но тогда рассмотрим прямоугольник(мы обращались к <tex>хx</tex>)А когда-то мы обратимся к <tex>уy</tex>

Если есть точка на левой стороне, то к <tex>хx</tex> мы обратимся раньше, чем к <tex>уy</tex> следовательно неверно, что приоритет <tex>хx</tex> больше чем приоритет <tex>уy</tex>

Если на нижней стороне есть точка, значит есть точка, к которой мы обращались сейчас, ключ которой больше, чем у <tex>хx</tex>, но меньше <tex>уy</tex>, но тогда она должна быть нашим правым сыном, а не вершина <tex>уy</tex>.