Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Range Query on Li Chao Tree ??

Правка en1, от ProdipDatta, 2020-05-31 13:09:46

Hi everyone
I know that in Li Chao Tree it is possible to add some line of the form (ax + b), in the tree and query for a maximum or minimum y-intercept in a specific point, x.
I want to know that Is it possible to query for a maximum y-intercept in a range of values,x ?
More specifically, is it possible to choose such a value x from the interval [l, r] such that x gives the maximum y-intercept with complexity less than or equal to O(sqrt(N)) where 1 <= l <= r <= N <= 106 ?.

Your any kind of information regarding the topic will be appreciated.
Thank you.

Теги #data structure, #li chao tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ProdipDatta 2020-05-31 13:09:46 710 Initial revision (published)