hackercupai/hackercup huggingface dataset:
As in the previous chapter, we can determine the tree structure of all the polygons. However, we can no longer process all query points as part of the first sweep, as this chapter requires them to be solved online.

We can use a [persistent binary search tree](http://courses.csail.mit.edu/6.854/06/scribe/s2-persistent.pdf) such as a persistent treap or persistent AVL-tree, which is a BST that's versioned over changes. Inserting and deleting new entries still take \(\mathcal{O}(\log N)\) time, but doing so in a new copy will only take \(\mathcal{O}(\log N)\) additional memory per operation instead of having to copy the whole tree. We can access any version of the tree in \(\mathcal{O}(1)\) as long as we have a pointer to its root.

Specifically, we will keep a version of our persistent BST for each \(x\) coordinate. We can store all the versions in a array, sorted by the \(x\)-coordinate they correspond to. Given a query point \((x, y)\), we can binary search for the right version. After obtaining the version, we can search for the line segment immediately below us, again the upper/lower convex-hull checks to determine the polygon ID containing that point. The rest of the solution is the same as in chapter 1.

Let \(V = \sum_i M_i\) be the total number of vertices. The time and space complexity to build and store all versions of the persistent BST is \(\mathcal{O}(V \log V)\). The time to find the polygon of a query point is \(\mathcal{O}(\log V)\) to first binary search for \(x\), plus another \(\mathcal{O}(\log V)\) to binary search at \(x\) for the segment immediately below \(y\). The overall hashes of nodes can again be checked in \(\mathcal{O}(1)\). Thus the overall time complexity across \(Q\) queries is \(\mathcal{O}((V + Q) \log V)\).