Prerequisite :
I guess that somebody maybe stuck in here, so, we will answer it later.
II.Problemstatement
You must give a data structure which can do two following operation by the best way you can :
- Add a line $$$y = a*x + b$$$ into set $$$S$$$
- Given an integer point $$$x$$$, find $$$min$$$ value of $$$y$$$ among all line we added
Similar to $$$Li-Chao$$$ $$$tree$$$, we manage convex hull by the way maintain a segment $$$[L, R]$$$, for each intergers $$$x$$$ in $$$[L, R]$$$ we store line $$$y = a*x + b$$$ such that the line $$$y = a*x + b$$$ reach min at point with coordinate $$$x$$$ among all of line.
Add operation :
We can reach two observation :
- Add two line $$$x = -\infty$$$ and $$$x = +\infty$$$ into $$$S$$$. Easy to see that the convex hull look like a parabol with nagative slope. $$$(*)$$$
- If a line lie on convex hull, it will lie on a continuous interval on convex hull. $$$(**)$$$
Thicker line represent the convex hull
We can iterate over $$$[L, R]$$$ whenever we add a new line into $$$S$$$ to update the «min line» for each point in $$$[L, R]$$$
However, by two observation above, we can do ternary search to find point $$$x$$$ such that:
Because $$$(**)$$$ then we also need a segment tree to range update (lazy propagation is recommend). Add operation is done!
Query operation : We only need get result on segment tree by go to leaf which represent point $$$x$$$. So easy, right?
III.Basic Li-Chao tree
I will explain following code in this blog : https://codeforces.com/blog/entry/86731 (code is in Prerequistes section)
Add operation : Instead of ternary serach and range update, we will search point with x-coordinate which at $$$x$$$, line $$$y = a*x + b$$$ lie on convexhull, we can «walk on segment tree» to find such $$$x$$$.
Back to the first question in I section. By storing in such way, we can get some observation :
- If a line lie on a contiguous interval on convex hull, it will be stored in some node on $$$Li-Chao$$$ $$$tree$$$. $$$(***)$$$
- If a line $$$y = a*x + b$$$ reach min in range $$$[L, R]$$$ among all line we added, then any path from root to every leaf $$$x$$$ $$$\in$$$ $$$[L, R]$$$ on $$$Li-Chao$$$ $$$tree$$$ $$$(****)$$$ will pass over at least one times the line $$$y = a*x + b$$$.
Query operation : by $$$(****)$$$, we get min value of $$$y = a*x + b$$$ on path from root to leaf, we will get the min result we want. Which answer the second question in I section. All done!
IV.Epilogue
That’s all thing I can think about $$$Li-Chao$$$ $$$tree$$$, so this is my first time to write something i have learn on codeforces, hope that my blog will not get nagative rate. Thanks for reading! (And sorry because my English)
Источник
Prerequisite :
I guess that somebody maybe stuck in here, so, we will answer it later.
II.Problemstatement
You must give a data structure which can do two following operation by the best way you can :
- Add a line $$$y = a*x + b$$$ into set $$$S$$$
- Given an integer point $$$x$$$, find $$$min$$$ value of $$$y$$$ among all line we added
Similar to $$$Li-Chao$$$ $$$tree$$$, we manage convex hull by the way maintain a segment $$$[L, R]$$$, for each intergers $$$x$$$ in $$$[L, R]$$$ we store line $$$y = a*x + b$$$ such that the line $$$y = a*x + b$$$ reach min at point with coordinate $$$x$$$ among all of line.
Add operation :
We can reach two observation :
- Add two line $$$x = -\infty$$$ and $$$x = +\infty$$$ into $$$S$$$. Easy to see that the convex hull look like a parabol with nagative slope. $$$(*)$$$
- If a line lie on convex hull, it will lie on a continuous interval on convex hull. $$$(**)$$$
Thicker line represent the convex hull
We can iterate over $$$[L, R]$$$ whenever we add a new line into $$$S$$$ to update the «min line» for each point in $$$[L, R]$$$
However, by two observation above, we can do ternary search to find point $$$x$$$ such that:
Because $$$(**)$$$ then we also need a segment tree to range update (lazy propagation is recommend). Add operation is done!
Query operation : We only need get result on segment tree by go to leaf which represent point $$$x$$$. So easy, right?
III.Basic Li-Chao tree
I will explain following code in this blog : https://codeforces.com/blog/entry/86731 (code is in Prerequistes section)
Add operation : Instead of ternary serach and range update, we will search point with x-coordinate which at $$$x$$$, line $$$y = a*x + b$$$ lie on convexhull, we can «walk on segment tree» to find such $$$x$$$.
Back to the first question in I section. By storing in such way, we can get some observation :
- If a line lie on a contiguous interval on convex hull, it will be stored in some node on $$$Li-Chao$$$ $$$tree$$$. $$$(***)$$$
- If a line $$$y = a*x + b$$$ reach min in range $$$[L, R]$$$ among all line we added, then any path from root to every leaf $$$x$$$ $$$\in$$$ $$$[L, R]$$$ on $$$Li-Chao$$$ $$$tree$$$ $$$(****)$$$ will pass over at least one times the line $$$y = a*x + b$$$.
Query operation : by $$$(****)$$$, we get min value of $$$y = a*x + b$$$ on path from root to leaf, we will get the min result we want. Which answer the second question in I section. All done!
IV.Epilogue
That’s all thing I can think about $$$Li-Chao$$$ $$$tree$$$, so this is my first time to write something i have learn on codeforces, hope that my blog will not get nagative rate. Thanks for reading! (And sorry because my English)
Источник