stopping_by_woods's blog

Problem on Li Chao Tree
By stopping_by_woods, history, 4 years ago, In English

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:

  1. add pair ($$$a$$$, $$$b$$$) to the set. ($$$-10^9$$$ $$$\le$$$ $$$a, b$$$ $$$\le$$$ $$$10^9$$$)

  2. remove a pair added in query $$$index$$$ (All queries are numbered with integers from $$$1$$$ to $$$n$$$).

  3. 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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This sounds like convex hull trick. https://codeforces.net/blog/entry/63823

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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)$$$.

→ Reply