We have an $x$-monotone path $\mathbb{P}$ in the input. We want to store the path $\mathbb{P}$ in a data structure such that we can answer this type of the query. Given any circle $\mathbb{C}$ and any two indices $i$ and $j$ with $1 \leq i \leq j \leq n$, report the first point of the subpath $\pi [ p_{i}, p_{j} ]=(p_{i},p_{i+1},...,p_{j}) $ is out of the $\mathbb{C}$.
We construct a balanced binary search tree storing the points $p_{1}, p_{2}, ... , p_{n}$ in its leaves. At each node of the tree, we store the extreme points of the convex hull of all points stored in its subtree.
To answer a query, we compute $\mathcal{O}(\log{}n)$ canonical nodes whose subtree span the vertices on the subpath $\pi [ p_{i}, p_{j} ]$. For each canonical node, we check whether or not the extreme points are in the $\mathbb{C}$. If all the extreme points lie inside $\mathbb{C}$, data structure reports $j$ otherwise it reports the first extreme point $L$ which is outside of the $\mathbb{C}$.
Now, I want to know what the worst Query time is.
