Can someone plz explain how to do this problem. Problem from the recent hackerearth contest
You are given n ($$$1$$$ $$$\le$$$ $$$n$$$ $$$\le$$$ $$$300000$$$) queries. Each query is one of $$$3$$$ types:
add pair ($$$a$$$, $$$b$$$) to the set. ($$$-10^9$$$ $$$\le$$$ $$$a, b$$$ $$$\le$$$ $$$10^9$$$)
remove a pair added in query $$$index$$$ (All queries are numbered with integers from $$$1$$$ to $$$n$$$).
For a given integer $$$A$$$ find the maximal value $$$a·A + b$$$ over all pairs ($$$a$$$, $$$b$$$) from the set. ($$$-10^9$$$ $$$\le$$$ $$$A$$$ $$$\le$$$ $$$10^9$$$). It is guaranteed that the set of pair will not be empty.
INPUT.
The first line contains integer $$$n$$$ ($$$1$$$ $$$\le$$$ $$$n$$$ $$$\le$$$ $$$3·10^5$$$) — the number of queries.
Each of next $$$n$$$ lines starts with integer $$$op$$$ ($$$1$$$ $$$\le$$$ $$$op$$$ $$$\le$$$ $$$3$$$) — the type of query.
OUTPUT
For each query of $$$3$$$ type print on a separate line the maximal value of $$$a·A + b$$$. It is guaranteed that the set of pair will not be empty.
This sounds like convex hull trick. https://codeforces.net/blog/entry/63823
Here's a tutorial for li chao tree. https://www.youtube.com/watch?v=-StmrE2gY44&t=1396s
Since adding elements is always $$$O(\log A)$$$, this can be implemented with rollbacks, in a way similar to persistent segment tree. You just have to maintain a vector of roots, and pop the last root to rollback changes.
https://cp-algorithms.com/data_structures/deleting_in_log_n.html
You can use this to maintain the lichao tree for each "time", or the number of queries that have passed.
We create a segment tree over time, where each node stores the points that were active throughout $$$l$$$ and $$$r$$$, but not for it's parent, where $$$l$$$ and $$$r$$$ is the range of the node. Each point will be on $$$O(\log n)$$$ nodes.
Now notice, that all points that existed at some time $$$t$$$, must be on some parent of $$$t$$$. So if we can maintain the points on the parents, we can do this quickly.
What we do here, is we dfs on the segment tree, while adding and popping the elements of the current node in the li chao tree. We will find the answer when we reach the leaf of time $$$t$$$. Since we visit each node once, each point will be popped and added $$$O(\log q)$$$ times, So giving us a final time complexity of $$$O(q\log q\log A)$$$.
Thanks for your reply. I need to first study the li chao tree, thanks for the link :)
.