Mowing the Field USACO Question

Правка en2, от dx24816, 2019-06-28 20:53:06

Hello,

I don't quite understand the editorial to Mowing the Field (http://www.usaco.org/index.php?page=viewproblem2&cpid=601). The solution they gave here (http://www.usaco.org/current/data/sol_mowing_platinum_jan16.html) claims that you can answer the range queries in originally log(n)^3 time. However, I don't understand why. For a specific vertical segment i, we want to find how many times it intersects a horizontal segment. I see how we can use a range query tree for the conditions y_i^b < y_j < y_i^t and abs(t_i — t_j) >= T. But I don't see how the range query tree can solve the part x_j^l < x_i < x_j^r as you're querying with i. In addition, I'm not quite clear on how you can update the range tree without having to update at each point on each horizontal line. Can anybody provide some help with these questions?

Edit: I have thought about this some more, and there is no way that I can think of to not have a n^2 on the complexity besides incorporating some for of line sweep. If I am wrong, can someone point out how to remove the n^2 with just the range tree as it says in the editorial without the use of a line sweep?

-dx24816

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский dx24816 2019-06-28 20:53:06 314
en1 Английский dx24816 2019-06-22 18:53:42 879 Initial revision (published)