Изменения

}}

1) Запрос вершины 3 : вершина 3

2) Запрос 2 : вершина 3 – вершина 1 – вершина 2

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

Если <tex>t = x</tex>, то есть <tex>x</tex> -- предок <tex>y</tex> в момент <tex>i</tex>-го запроса,

тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.

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

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

Итак, tango-деревья

Пусть изначально все левые ребра были жирными.

В общем случае одно жирное, другое нет

Все наше дерево можно разбить на жирные пути

Каждый из этих жирных путей организуем в свое splay-дерево.

Из каждой вершины будет выходить вспомогательная ссылка на корень splay-дерева, соответствующего жирному пути в котором лежит тот ее ребенок, в которой ведет из нее нежирное ребро.

Таким образом, все наши ключи организуют иерархичную структуру.